fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define in(n) scanf("%d",&n)
  4. #define pb push_back
  5. #define N 1005
  6. #define pr(n) printf("%d ",n)
  7. #define out(n) printf("%d\n",n)
  8. vector<vector<int> > ad(N);
  9. int po[12],ar[4*N],lev[N],sp[2*N][11],vp[2*N],fist[N];
  10. int c;
  11. void dfs(int s)
  12. {
  13.     fist[s]=c,vp[c]=s,c++;
  14.     int i,x=ad[s].size();
  15.     for(i=0;i<x;i++)
  16.         lev[ad[s][i]]=lev[s]+1,dfs(ad[s][i]),vp[c]=s,c++;
  17.     return ;
  18. }
  19. void up(int j,int n)
  20. {
  21.     sp[j][0]=vp[j];
  22.     for(int k=1;k<12;k++)
  23.         if(j+po[k]<=n)sp[j][k]=lev[sp[j][k-1]]<lev[sp[j+po[k-1]][k-1]]?sp[j][k-1]:sp[j+po[k-1]][k-1];
  24.     return ;
  25. }
  26. int query(int a,int b)
  27. {
  28.     int y,x=b-a+1;
  29.     y=ar[x],x-=po[y];
  30.     return lev[sp[a][y]]<lev[sp[a+x][y]]?sp[a][y]:sp[a+x][y];
  31. }
  32. int main()
  33. {
  34.     int k,i,t,w,n,x,a,b,q,j;
  35.     ar[1]=0,k=1,po[0]=1;
  36.     while(k<2*N)
  37.     {
  38.         for(i=k+1;i<2*k;i++)
  39.             ar[i]=ar[k];
  40.         ar[2*k]=1+ar[k],k*=2;
  41.     }
  42.     for(i=1;i<12;i++)
  43.         po[i]=2*po[i-1];
  44.     in(t);
  45.     for(w=1;w<=t;w++)
  46.     {
  47.         in(n),c=0;
  48.         for(i=0;i<n;i++)
  49.         {
  50.             in(x);
  51.             ad[i].resize(x);
  52.             for(j=0;j<x;j++)
  53.                 in(a),ad[i][j]=a-1;
  54.         }
  55.         lev[0]=0,dfs(0);
  56.         for(int i=c-1;i>=0;i--)
  57.             up(i,c);
  58.         printf("Case %d:\n",w);
  59.         in(q);
  60.         while(q--)
  61.         {
  62.             in(a),in(b);
  63.             x=1+query(min(fist[a-1],fist[b-1]),max(fist[a-1],fist[b-1]));
  64.             out(x);
  65.         }
  66.     }
  67. }
  68.  
Success #stdin #stdout 0s 3004KB
comments (?)
stdin
copy 
1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7
stdout
copy 
Case 1:
3
1
https://ideone.com/ZNl6F7
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!