fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAXN 2000
  4. int block_sz;
  5. int depth[MAXN];
  6. int parent[MAXN];
  7. int jump_parent[MAXN];
  8. int hmax;
  9. ///jump_parent is first ancestor
  10. ///of current node
  11.  
  12. vector <int> adj[MAXN];
  13. void addEdge(int u,int v){
  14.     adj[u].push_back(v);
  15.     adj[v].push_back(u);
  16. }
  17.  
  18. int lca_naive(int u,int v){
  19.     if(u==v){
  20.         return u;
  21.     }
  22.     if(depth[u]>depth[v])
  23.         swap(u,v);
  24.     v=parent[v];
  25.     return lca_naive(u,v);
  26. }
  27. void dfs(int cur,int prev){
  28.     depth[cur]=depth[prev]+1;
  29.     parent[cur]=prev;
  30.     //hmax=max(height,hmax);
  31. ///suppose if h=9,then sqrt(h)=3
  32. ///in that case total blocks will be
  33. ///0 to 3-1
  34. /// so rem will be zero for only first element in the current block
  35.     if(depth[cur] % block_sz == 0){
  36.         jump_parent[cur]=parent[cur];
  37.     }
  38.     else{
  39.         jump_parent[cur]=jump_parent[prev];
  40.     }
  41.     for(int i=0;i<adj[cur].size();i++){
  42.         if(adj[cur][i]!=prev){
  43.             dfs(adj[cur][i],cur);
  44.         }
  45.     }
  46. }
  47. int lcasqrt(int u,int v){
  48.     while(jump_parent[u]!=jump_parent[v]){
  49.         if(depth[u]>depth[v])
  50.             swap(u,v);
  51.         v=jump_parent[v];
  52.     }
  53.     return lca_naive(u,v);
  54. }
  55. void preprocess(int height){
  56.     block_sz=sqrt(height);
  57.     depth[0]=-1;
  58.  
  59.     dfs(1,0);
  60. }
  61. void dfs_height(int cur,int prev,int height){
  62.     hmax=max(height,hmax);
  63.     for(int i=0;i<adj[cur].size();i++){
  64.         if(adj[cur][i]!=prev)
  65.             dfs_height(adj[cur][i],cur,height+1);
  66.     }
  67. }
  68. int main(int argc, char const *argv[])
  69. {
  70.     // adding edges to the tree
  71.     int t;
  72.     cin>>t;
  73.     while(t--){
  74.         int n;
  75.         cin>>n;
  76.         for(int i=1;i<=n;i++){
  77.             int m;
  78.             cin>>m;
  79.             for(int j=1;j<=m;j++){
  80.                 int v;
  81.                 cin>>v;
  82.  
  83.                 adj[i].push_back(v);
  84.             }
  85.         }
  86.         dfs_height(1,0,0);
  87.         preprocess(hmax+1);
  88.         dfs(1,0);
  89.         int q;
  90.         cin>>q;
  91.         for(int i=0;i<q;i++){
  92.             int u,v;
  93.             cin>>u>>v;
  94.             cout<<lcasqrt(u,v)<<endl;
  95.  
  96.         }
  97.  
  98.  
  99.     }
  100. }
  101.  
Success #stdin #stdout 0s 15304KB
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 
3
1
https://ideone.com/Q6AbaO
problem LCA, based on SPOJ submission 23429401 (CPP14), 2019-03-17 10:49:08
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!