My algorithm:

I run BFS to assign levels (DISTANCE TO THE ROOT) to each node.

Then, when read the queries:
If the level of both nodes are the same, no exist any path between them. Answer is 0
If the level of qA is less than level of qB, maybe exist a path between them. Find it.
If found a path, Answer is 1
If no path had been found, and the level of qA is greater than level of qB, Find a path.
If found a path, Answer is 2
If none of the previous worked, the answer to the querie is 0.


I read that it could be solved with LCA, but I think that it's better and elegant algo.
Please help me. Maybe my algo is right, but my problem may be on the code. If need to see code, i'll post it.

solved :x

Edited by author 26.03.2012 03:51

If you get WA2 try this one:
Input:
3
3 2
2 1
1 -1
3
1 2
3 2
1 3
Output:
1
2
1

Also if you get WA12 pay attention for: "All identifiers lie between 0 and 40000."

I try to solve it for O(n * log(n) * log(n)). I don't understand why I can't passed it? Please help me. I can send my code.

Edited by author 11.03.2007 15:15

please help, give me some exemples
if
descendant(A,B)==true, if A is descendant for B
int level(int X) == level of vertex with number X,
level(root)==0

my code:
...

    for (i=0;i<L;i++)
    {
        int a,b;
        scanf("%i %i",&a,&b);
        if (a==b){printf("0\n");continue;}
        if (level(a)<level(b))
        {
            if (descendant(b,a)) printf("1\n");
            else printf("0\n");
        }
        else
        {
            if (descendant(a,b)) printf("2\n");
            else printf("0\n");
        }
    }

WHY I got WA14?
please help me

IMHO, it's one of the best problemsm that helps you teaching STL.

After having 'Stack Overflow', now i have WA 42 and I don't know, why! Could you give me some tests or hints,please!

If somebody know how to make my variant working faster(if it's possible), please write to nonename@narod.ru.
 I think in the worst case it needs O(n*l), but I also think  it's quite clear to understand. May be using memory will be faster, but haven't tried. Other variant is that algorithm is wrong.



  int i,j,n,l;
  int work[40005];

  cin >> n;

  work[0]=-1;
  for (i=0;i<n;i++){
    int tmp;
    cin >> tmp;
    cin >> work[tmp+1];
  }
  cin >> l;
  int a,b,fl=0;
  for (i=0;i<l;i++){
    fl=0;
    cin >> a >> b;
    int wka=a;
    int wkb=b;
    while (wka+wkb+2){
        wka=work[wka+1];
        wkb=work[wkb+1];
      if (wka==b){
        fl=2;
        break;
      }
      if (wkb==a){
        fl=1;
        break;
      }
    }
   cout << fl << endl;
  }

If you have CRASH, may be, will help for you to make columns of a global variable and to clean from definitions of procedures. I got AC...

Wrong Answer On Test 1

help...

#include <fstream>
#include <iostream>
using namespace std;

int main(void) {
    long int st[40001], n, l, a, b, i, j;

    cin >> n;

    for (i=0; i<40001; i++)
        st[i] = -2;

    for (i=0; i<n; i++) {
        cin >> a >> b;
        st[a] = b;
    }

    cin >> l;

    for (j=0; j<l; j++) {
        cin >> a >> b;

        i = a;
        while (i >= 0 && i != b)
            i = st[i];

        if (i == b) {
            cout << "2\n";
            continue;
        }

        i = b;
        while (i >= 0 && i != a)
            i = st[i];

        if (i == a) {
            cout << "1\n";
            continue;
        }

        cout << "0\n";
    }
    return 0;
}

"Файл input.txt содержит ..."

Adding this simple fragment

procedure search2(d: longint);
begin
   if d <= 50000 then
      search2(d + 1);
end;
............
search2(0);

I turn Stack Overflow 29 into SO1.
Is it mean, that I must avoid recursion in this task? How much stack size?

Edited by author 30.08.2005 14:10

Why the hell this c program gets TLE on test 1? It works perfectly on sample.

#include <stdio.h>

int main()
{
    int ar[40000],n,i,a,b,l,ta,tb;
    char o[40000];
    //freopen("in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;i++)
        ar[i]=0;
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        a--;
        ar[a]=b;
    }
    scanf("%d",&l);
    for(i=0;i<l;i++)
    {
        scanf("%d%d",&a,&b);
        a--;
        b--;
        ta=a;
        tb=b;
        while(ta!=-1&&ta!=b&&ta!=0)
            ta=ar[ta]-1;
        if(ta==b)
        {
            o[i]=2;
            //printf("2\n");
            continue;
        }
        while(tb!=-1&&tb!=a&&ta!=0)
            tb=ar[tb]-1;
        if(tb==a)
        {
            o[i]=1;
            //printf("1\n");
            continue;
        }
        o[i]=0;
        //printf("0\n");
    }
    for(i=0;i<l;i++)
        printf("\n%d",o[i]);
    return 0;
}

As I understand, we should remember all the sons of a current node. To do it we should use either [40000][40000] or dynamic structures... We can't make DFS fast if we remember only fathers, am I right?

C++ Program:
#include  <stdio.h>

int  main()
{
  long  st[40005], n, l, a, b, i, j;

  for  (i = 0;  i < 40005;  ++i)
    st[i] = -2;

  scanf("%ld", &n);
  for  (i = 0;  i < n;  ++i) {
    scanf("%ld%ld", &a, &b);
    st[a] = b;
  }

  scanf("%ld", &l);
  for  (j = 0;  j < l;  ++j) {

    scanf("%ld%ld", &a, &b);

    if  (j > 0)  printf("\n");

    i = a;
    while  (i >= 0) {
      i = st[i];
      if  (i == b)  break;
    }
    if  (i == b)  {printf("2");  continue;}

    i = b;
    while  (i >= 0) {
      i = st[i];
      if  (i == a)  break;
    }
    if  (i == a)  {printf("1");  continue;}

    printf("0");
  }

  return  0;
}





Pascal Programm:
var  l, i, j, n, a, b: longint;
     st: array[0..40000] of longint;

begin

for  i := 0  to  40000  do
  st[i] := -2;

readln(n);
for  i := 1  to  n  do  begin
  readln(a, b);
  st[a] := b;
end;

readln(l);
for  j := 1  to  l  do  begin
  readln(a, b);

  i := a;
  while  i >= 0 do begin
    i := st[i];
    if  (i = b)  then   break;
  end;
  if  i = b  then  begin writeln(2); continue; end;

  i := b;
  while  i >= 0 do begin
    i := st[i];
    if  (i = a)  then   break;
  end;
  if  i = a  then  begin writeln(1); continue; end;

  writeln(0);
end;

end.

In this problem in input data must be TREE, because in input write:" The input file contains full history TREE description...". But it is not a tree, because there are cycle...

Hey! I've lost about 30 minutes to run my program under 3MB. I am sure that my program don't use more than 3MB. Your online judge have some troubles with determinating Memory Usage of PASCAL programs. Please fix it. (I mean set Memory Limit = 5MB)