fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int N = 23;
  6. const int maxn = 1005;
  7. vector<int> g[maxn];
  8. int bin[maxn][N];
  9. bool bio[maxn];
  10. int dist[maxn];
  11. vector<int> rt;
  12.  
  13. int t,n,q,ciner,m,a,b,c=0,ans=0,r;
  14.  
  15. void dfs(int x,int y){
  16.     if(bio[x]) return;
  17.     dist[x]= dist[y]+1;
  18.     bin[x][0] = y;
  19.     bio[x] = true;
  20.     for(int i = 0; i < g[x].size(); i++){
  21.         dfs(g[x][i],x);
  22.     }
  23.  
  24.  
  25. }
  26.  
  27.  
  28. int main(){
  29.     cin >> t;
  30.     for(int _ = 0; _ < t; _++){
  31.         ans=0;
  32.         memset(bin,0,sizeof(bin));
  33.         memset(bio,false,sizeof(bio));
  34.         memset(dist,0,sizeof(dist));
  35.         rt.clear();
  36.         // memset(g,{},sizeof(g));
  37.  
  38.  
  39.  
  40.         cin >> n;
  41.         for(int i = 0; i<n; i++){
  42.             g[i].clear();
  43.         }
  44.         for(int i = 0; i<n; i++){
  45.  
  46.  
  47.             cin >> m;
  48.             for(int j = 0; j<m; j++){
  49.                 cin >> ciner;
  50.                 ciner--;
  51.                 g[i].push_back(ciner);
  52.                 rt.push_back(ciner);
  53.  
  54.  
  55.             }
  56.  
  57.         }
  58.         sort(rt.begin(),rt.end());
  59.         for(int i = 0; i<n-1; i++){
  60.             // cout << i << " " << rt[i] << endl;
  61.             if(i!=rt[i]){
  62.                 r=i;
  63.                 break;
  64.             }
  65.  
  66.         }
  67.  
  68.         cin >> q;
  69.  
  70.         dfs(r,0);
  71.  
  72.         for(int i = 0; i<n; i++){
  73.             for(int j = 1; j<N; j++){
  74.                 bin[i][j] = bin[bin[i][j-1]][j-1];
  75.             }
  76.         }
  77.         cout << "Case " << _+1 << ":\n";
  78.         while(q--){
  79.             cin >> a >> b;
  80.             a--; b--;
  81.             c = abs(dist[a]-dist[b]);
  82.             if(dist[a]>dist[b]){
  83.                 for(int i = 1; c>=0;i++){
  84.                     if(c&i){
  85.                         a=bin[a][i-1];
  86.                         c-=(2 << i);
  87.                     }
  88.                 }
  89.  
  90.             }
  91.             if(dist[a]<dist[b]){
  92.                 for(int i = 1; c>=0;i++){
  93.                     if(c&i){
  94.                         b=bin[b][i-1];
  95.                         c-=(2 << i);
  96.                     }
  97.                 }
  98.  
  99.             }
  100.             if(a==b){
  101.                 cout << a+1 << '\n';
  102.             }
  103.             // cout << dist[a] << " " << dist[b] << endl;
  104.  
  105.  
  106.             else{
  107.                 for(int i = N-1; i>=0; i--){
  108.                     if(!(bin[a][i]==bin[b][i])){
  109.                         a=bin[a][i];
  110.                         b=bin[b][i];
  111.  
  112.                     }
  113.                 }
  114.                 cout << bin[a][0]+1 << '\n';
  115.             }
  116.  
  117.  
  118.  
  119.         }
  120.  
  121.         // for(int i = 0; i<n; i++){
  122.         //     for(int j = 0; j<N; j++){
  123.         //         cout << bin[i][j] << " ";
  124.         //     }
  125.         //     cout << '\n';
  126.         // }
  127.  
  128.  
  129.  
  130.     }
  131.  
  132. }
  133.  
Success #stdin #stdout 0.01s 5324KB
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/EAWhsk
language:
C++ (gcc 8.3)
created:
16 hours 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!