Notice, that +1 and -1 mean not victory and defeat states.

INPUT
2
L 1 +1

OUTPUT
+1

var
  f,q,be:array[0..1000] of integer;
  n,x,a,b,c:integer;
  m:char;
begin
{assign(input,'1282.txt');
reset(input);
}  readln(n);
  for x:=1 to n do
    be[x]:=-3;
  for x:=2 to n do
    begin
      read(m);
      if m='L' then
        begin
          readln(a,b);
          if be[a]=-3 then
            begin
              inc(c);
              q[c]:=a;
              be[a]:=-1;
            end;
          if b=-1 then be[a]:=1;
          if (b=0) and (be[a]<0) then be[a]:=0;
        end
      else
        readln(f[x]);
    end;
  b:=1;
  while q[b]<>1 do
    begin
      if be[f[q[b]]]<-2 then
        begin
          inc(c);
          q[c]:=f[q[b]];
          be[f[q[b]]]:=-1;
        end;
      if be[q[b]]=-1 then be[f[q[b]]]:=1;
      if (be[q[b]]=0) and (be[f[q[b]]]<0) then be[f[q[b]]]:=0;
      inc(b);
    end;
  if be[1]=1 then writeln('+1') else writeln(be[1]);
end.
{be[n]==the best value it then player play best
f[n]==the father of n
be[n]=-3===>it hasn't been visited
}

Edited by author 29.12.2015 22:25

What is on 18 test?

I don't understand the 2nd sample test.
Is a player go on the path from where the othe player reach?
Or are the players move on different path?

Hint for you :

int travel(int player,int node)
{
    int value;

    if(isLeaf(node)) return getValue(node);

    // If the first player is at this node, he prefer getting the maximal value among -1, 0 and +1.
    if(player == 0)
    {
        value = MinValue();
        for(int a=0;a<numberOfChild(node);a++)
        {
            int v = travel((player+1)%2,getChild(node,a));
            if(value < v) value = v;
        }
    }
    // Get the minimal value.
    else
    {
        value = MaxValue();
        for(int a=0;a<numberOfChild(node);a++)
        {
            int v = travel((player+1)%2,getChild(node,a));
            if(value > v) value = v;
        }
    }
    return value;
}

Edited by author 24.02.2011 15:14

Edited by author 24.11.2010 23:13

I don't understand this problem. As I think, the third sample is the tree from the picture. But I can not understand why, for example, 'the number of the ancestor of this node' for the node #18 is 12? What does it mean, 'the number of the ancestor of this node'?

THank you.

I get WA 10 and I'm really confused why???
I use simply algo: BFS of the tree and I make simulation of the right strategy.

Can you help me? Can you give me some test data? Or a hint?

In 1282 the image is empty (X).