type pver=^tver;
     pe=^te;
     te=record
      e:pe;
      ver:pver;
     end;
     tver=record
      s:string;
      e:pe;
     end;
type trec=record
      s:string;
      ver:pver;
     end;
var i,n:word;
    s:string;
    pb,ver:pver;
    fir:boolean;
procedure add(s:string;ver:pver);
var e:pe;
    vt:pver;
begin
 if s='' then exit;
 e:=ver^.e;
 while e<>nil do begin
  if copy(s,1,pos('\',s)-1)=e^.ver^.s then begin
   delete(s,1,pos('\',s));
   add(s,e^.ver);
   exit;
  end;
  e:=e^.e;
 end;
 new(vt);
 vt^.e:=nil;
 if pos('\',s)>0 then vt^.s:=copy(s,1,pos('\',s)-1) else
 vt^.s:=s;
 new(e);
 e^.ver:=vt;
 e^.e:=ver^.e;
 ver^.e:=e;
 if pos('\',s)>0 then begin
  delete(s,1,pos('\',s));
  add(s,vt);
 end;
end;
procedure writ(ver:pver;ur:word);
var a:array [1..600] of trec;
    t:trec;
    kol,u,i:word;
    e:pe;
begin
 kol:=0;
 e:=ver^.e;
 while e<>nil do begin
  inc(kol);
  a[kol].s:=e^.ver^.s;
  a[kol].ver:=e^.ver;
  e:=e^.e;
 end;
 if kol=0 then exit;
 for u:=1 to kol-1 do
 for i:=1 to kol-u do if a[i].s>a[i+1].s then begin
  t:=a[i];
  a[i]:=a[i+1];
  a[i+1]:=t;
 end;
 for i:=1 to kol do begin
{  if not fir then writeln;
  fir:=false;}
  for u:=1 to ur do write(' ');
  writeln(a[i].s);
  writ(a[i].ver,ur+1);
 end;
end;
begin
 new(pb);
 pb^.e:=nil;
 readln(n);
 for i:=1 to n do begin
  readln(s);
  add(s,pb);
 end;
 fir:=true;
 writ(pb,0);
end.

Any ideas?

Double post.
Wrong!
please delete this post.

Edited by author 23.07.2010 02:19

Edited by author 23.07.2010 02:19

Try this:
2 1 2 2 2 3 3
0

Right answer:
2 1 2 2 2 3 3

I had WA, and now I have AC!

Edited by author 01.10.2007 20:17

Edited by author 01.10.2007 20:17

Please, help me with test 2. Can you say me, how much my answer differs from correct answer?

Who can tell me?
I have WA1.
Thanks a lot.

Edited by author 03.05.2009 09:55

Edited by author 03.05.2009 09:56

Edited by moderator 13.05.2009 01:51

with such a large ML?

Edited by author 25.04.2012 19:42

You can consider that the cost of the tunnel is 1, and the bridge is 24000. Then it becomes a MST problem.

use         while (getchar()!='\n');
don't use        scanf("\n");
scanf("\n") not just wait for \n ,it will skip all blank char

Edited by author 11.05.2009 10:57

sort + BigInteger

this algo with O(n*log(n))
but i don't know why WA on Test21, please help me!

[code deleted]

Edited by moderator 24.11.2019 13:39

Which problems on Timus I can solve using suffix trees/arrays?
Thx.

[code deleted]

sorry.stupid mistake.AC

Edited by author 20.07.2010 18:09

Is it possible to solve this problem using suffix tree? or it will get MLE?

For example,

xxx┌────┐xxxxx
xxx│xxxxxx│x┌──┐
xxx│xxxxxx│x│xxx│
xxx│xxxxxx│x│xxx│
xxx│xxxxxx│x└──┘
xxx└────┘xxxxx

Should I output the left first, or the right first?

Edited by author 19.07.2010 15:39

Here is my program:program Space;
  var L, R, I, J, K : longint;
      s : array [1.. 1000] of longint;
  begin
    readln (L);
    if L < 2 then R := 0;
    for I := 1 to 1000 do s [I] := 0;
    if L > 1 then
      begin
        I := 2;
        J := 2;
        s [1] := 2;
        R := 1;
        repeat
          if L > J then
            begin
              inc (R);
              s [R] := I;
              if R > 3 then inc (s [R]);
              I := J + 1;
              J := (I + 2 - s [R]) * s [R] - 2;
            end;
        until L <= J;
      end;
    writeln (R);
    for I := R downto 1 do writeln (s [I]);
  end.

I didn't notice it!

This is my code.
I don't know why got the WA #2.
But When I use the sample in the forum, I got the same answer as result in the forum.

Could someone tell my which place take wrong?
I really appreciate you.


#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct{
    int right;
    int left;
    int index;
    int win;
    int lose;
}segment;


int contain(segment a,segment b){
    if (a.left > b.left  &&  a.right < b.right ) return 1;
    else return 0;
}


int main(){

    int i,j,m,num;
    segment point[500],tmp;
    memset(point , '\0' , sizeof(point) );

    scanf("%d",&num);
    if(num < 0 || num > 500) exit(0);

    for(i = 0 ; i <  num ; i++){
        scanf("%d %d",&point[i].left , &point[i].right );
        if(point[i].left > 10000 || point[i].left < -10000) exit(0);
        else if(point[i].right > 10000 || point[i].right < -10000) exit(0);
        point[i].index = i;
    }

    for(i = 0 ; i < num ; i++){
        if(point[i].left > point[i].right){
                           m = point[i].left;
               point[i].left = point[i].right;
              point[i].right =  m ;
        }
    }
/*
   for(i = 0 ; i < num ; i ++){
       printf("%2d %2d\n",point[i].left , point[i].right);
   }
*/
   for (i = 0 ; i <  num ; i++){
        for(j = 0; j < num; j++){
               if( ( i != j )   &&   (  contain( point[i] , point[j] )  )   ){
  /*                  printf("i = %d j = %d \n" , i, j);      */
                      point[i].lose ++;
                      point[j].win ++;
               }
        }
   }
/*
   for(i = 0 ; i < num ; i ++){
       printf("%2d %2d\n",point[i].win , point[i].lose);
   }
*/
   for(i = 0 ; i < num ; i ++){
         for(j = i ; j < num ; j++ ){
                 if ( point[i].lose  <  point[j].lose ){

                         tmp = point[i];
                    point[i] = point[j];
                    point[j] = tmp ;
                 }
         }
   }

   for(i = point[0].lose  ; i < num ; i ++){
         for(j = i ; j < num ; j++ ){
                 if ( point[i].win  <  point[j].win ){
                         tmp = point[i];
                    point[i] = point[j];
                    point[j] = tmp ;
                 }
         }
   }

   printf("%d\n",point[0].lose + 1);

   for(i = 0 ; i <= point[0].lose  ; i ++){
       printf("%d ",point[i].index+1);
   }

return 0;
}

Can anybody help me with this test, please ?