In fact it's wrong! I've read your message and got WA two times!!! It have to be exactly one child said it was him!

/*AC*/
double time = 0.14;
long memory = 349; //КБ
return;

I am not use your idea!!!

No optimization!!!

Edited by author 25.07.2005 14:03

Edited by author 25.07.2005 14:04

Edited by author 25.07.2005 14:05

I too get WA#3 to this one, here is my C solution:

#include<stdio.h>
#define true 1
#define false 0
main()
{
 int parent[25001] , T , temp , temp2 , temp3 , test;
 int N , answer , cur;
 int confess , resolved;
 scanf("%d" , &T);
 for(test = 1 ; test <= T ; test++)
 {
  scanf("%d" , &N);
  confess = resolved = false;
  for(temp = 1 ; temp <= N ; temp++)
   parent[temp] = -1;
  for(temp = 1 ; temp <= N && resolved == false ; temp++)
  {
   scanf("%d" , &answer);
   if(answer == 0)
   {
    if(confess) { printf("NO\n"); resolved = true; }
    else confess = true;
   }
   else
   {
    cur = temp;
    while(cur != -1 && cur != answer) cur = parent[cur];
    if(cur == answer){  printf("NO\n") ; resolved = true; }
    else parent[answer] = temp;
   }
  }
  if(resolved == false)
   printf("YES\n");
  for( ; temp <= N ; temp++)
   scanf("%d" , &answer);
 }
}



Edited by author 24.05.2005 19:04

NO (Cycle: 3,1)
NO (Cycle: 4,3,2)

You need to use the O(n) algo. Here is my AC solution.
It checks if the graph is the tree. If is then YES.


program Collective_Guarantee;
const MaxN=25000;
label fin;
type List=array[1..MaxN] of Integer;
var  Tree,Sign:List;
     N,i,j,z,K,M,m1:integer;
     res:boolean;
begin
     readln(M);
for m1:=1 to M do
begin readln(N);
     z:=0;
     res:=true;
     for i:=1 to N do
     begin
          read(Tree[i]);
          if Tree[i]=0 then
            inc(z);
     end;
     if z<>1 then
     begin
          res:=false;
          goto fin;
     end else
     begin
           FillChar(Sign,SizeOf(Sign),0);
          K:=0;
          while true do
          begin
               i:=1;
               inc(K);
                 while (Sign[i]>0) and (i<=N) do
                  inc(i);
               if i<>N+1 then
               begin
                       while i<>0 do
                       begin
                         if Sign[i]=0 then
                            Sign[i]:=K else
                         if Sign[i]=K then
                         begin
                              res:=false;
                              goto fin;
                         end else
                         if Sign[i]<K then
                           i:=0;
                         if i<>0 then
                           i:=Tree[i];
                    end;
               end else
                goto fin;
           end;
     end;
fin: if res=false then
        writeln('NO') else
        writeln('YES');
end;
end.