fork(1) 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.         //cout<<a<<endl;
  48.         //cout<<ancestor[0][a]<<endl;
  49.  
  50.         //int x=ancestor[0][a];
  51.         cout<<"hola";
  52.         //a=x;
  53.     }
  54.     return a;
  55. }
  56. int main()
  57. {
  58.     int t;
  59.     cin>>t;
  60.     while(t--){
  61.         memset(lv,0,sizeof(lv));
  62.         cin>>n;
  63.         for(int i=1;i<=n;i++){
  64.             adjList[i].clear();
  65.         }
  66.         for(int i=1;i<=n;i++){
  67.             int m;
  68.             cin>>m;
  69.             while(m--){
  70.                 int a;
  71.                 cin>>a;
  72.                 adjList[i].push_back(a);
  73.                 adjList[a].push_back(i);
  74.             }
  75.         }
  76.         buildAncestor();
  77.         int q;
  78.         cin>>q;
  79.         while(q--){
  80.             int a,b;
  81.             cin>>a>>b;
  82.             //cout<<LCA(a,b)<<'\n';
  83.         }
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 4392KB
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 
Standard output is empty
https://ideone.com/d2hkpN
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!