fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define log_n 11
  4. #define debug(x) cout<<#x<<" = "<<x<<endl
  5. int n;
  6. vector<int> adjList[10005];
  7. int ancestor[15][10005];
  8. int lv[1005];
  9. void dfs(int u,int e,int depth)
  10. {
  11.     lv[u]=depth;
  12.     ancestor[0][u]=e;
  13.     for(int v: adjList[u]){
  14.         if(v==e) continue;
  15.         dfs(v,u,depth+1);
  16.     }
  17. }
  18. void buildAncestor()
  19. {
  20.     dfs(1,0,1);
  21.     for(int i=1;i<=log_n;i++){
  22.         for(int u=1;u<=n;u++){
  23.             ancestor[i][u]=ancestor[i-1][ ancestor[i-1][u] ];
  24.         }
  25.     }
  26. }
  27. int upward(int u,int d)
  28. {
  29.     for(int i=log_n;i>=0;i--){
  30.         if(d & (1<<i)){
  31.             u=ancestor[i][u];
  32.         }
  33.     }
  34.     return u;
  35. }
  36. int LCA(int a,int b)
  37. {
  38.     if(lv[a]>lv[b]) swap(a,b);
  39.     b=upward(b,lv[b]-lv[a]);
  40.     if(a!=b){
  41.         for(int i=log_n;i>=0;i--){
  42.             if(ancestor[i][a]!=ancestor[i][b]){
  43.                 a=ancestor[i][a];
  44.                 b=ancestor[i][b];
  45.             }
  46.         }
  47.         a=ancestor[0][a];
  48.     }
  49.     return a;
  50. }
  51. int main()
  52. {
  53.     int t;
  54.     cin>>t;
  55.     int c=0;
  56.     while(t--){
  57.         cout<<"Case "<<++c<<":\n";
  58.         memset(lv,0,sizeof(lv));
  59.         cin>>n;
  60.         for(int i=1;i<=n;i++){
  61.             adjList[i].clear();
  62.         }
  63.         for(int i=1;i<=n;i++){
  64.             int m;
  65.             cin>>m;
  66.             while(m--){
  67.                 int a;
  68.                 cin>>a;
  69.                 adjList[i].push_back(a);
  70.                 adjList[a].push_back(i);
  71.             }
  72.         }
  73.         buildAncestor();
  74.         int q;
  75.         cin>>q;
  76.         while(q--){
  77.             int a,b;
  78.             cin>>a>>b;
  79.             cout<<LCA(a,b)<<'\n';
  80.         }
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0s 4460KB
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/kwXqs4
language:
C++ (gcc 8.3)
created:
4 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!