fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fast   ios_base::sync_with_stdio(0), cin.tie(0);
  4. using namespace std;
  5.  
  6. const int N = 1005;
  7.  
  8. ll up[N][12], pa[N], h[N], lg[N];
  9. vector<ll> g[N];
  10.  
  11. void dfs(ll u){
  12.  for(auto v:g[u]){
  13.     if(v==pa[u]) continue;
  14.     pa[v]=u;
  15.     h[v]=h[u]+1;
  16.     dfs(v);
  17.  }
  18. }
  19. void wow(){
  20.     lg[0]=1;
  21.     for(int i=1;i<=12;i++)
  22.         lg[i]=lg[i-1]*2;
  23.  
  24.     for(int i=1;i<=N;i++)
  25.      if(lg[i]==0) lg[i]=lg[i-1];
  26. }
  27. void siu(ll n){
  28.  
  29.  
  30. for(int i=1;i<=n;i++) up[i][0]=pa[i];
  31.  
  32.  for(int j=1;j<=17;j++)
  33.   for(int i=1;i<=n;i++)
  34.    up[i][j]=up[up[i][j-1]][j-1];
  35.  
  36. }
  37.  
  38. ll adu(int u, int v) {
  39.     if (h[u] != h[v]) {
  40.         if (h[u] < h[v]) swap(u, v);
  41.  
  42.         int k = h[u] - h[v];
  43.         for (int j = 0; (1 << j) <= k; ++j)
  44.             if (k >> j & 1)
  45.                 u = up[u][j];
  46.     }
  47.     if (u == v) return u;
  48.  
  49.     int k = lg[h[u]];
  50.     for (int j = k; j >= 0; --j)
  51.         if (up[u][j] != up[v][j])
  52.             u = up[u][j], v = up[v][j];
  53.     return up[u][0];
  54. }
  55. int main()
  56. {
  57.   fast
  58.   wow();
  59.  
  60.   ll t;
  61.   cin>>t;
  62.  for(int test=1;test<=t;test++){
  63.     ll n,m;
  64.     cin>>n>>m;
  65.     for(int u=1;u<=n;u++){
  66.        ll k;
  67.        cin>>k;
  68.        while(k--){
  69.         ll v;
  70.         cin>>v;
  71.         g[u].push_back(v);
  72.         g[v].push_back(u);
  73.        }
  74.     }
  75.     h[1]=0;
  76.     dfs(1);
  77.  
  78.     pa[1]=1;
  79.     siu(n);
  80.  cout<<"Case " <<test<<":"<<"\n";
  81.     ll q;
  82.     cin>>q;
  83.     while(q--){
  84.         ll u,v;
  85.         cin>>u>>v;
  86.         cout<<adu(u,v)<<"\n";
  87.     }
  88.     for(int i=1;i<=n;i++) g[i].clear();
  89.   }
  90.     return 0;
  91. }
  92. /*
  93. 19
  94. 2 2 3
  95. 3 8 9 10
  96. 5 4 5 11 13 18
  97. 2 6 19
  98. 0
  99. 2 7 16
  100. 0
  101. 1 12
  102. 1 15
  103. 1 14
  104. 0
  105. 0
  106. 1 17
  107. 0
  108. 0
  109. 0
  110. 0
  111. 0
  112. 0
  113. 12
  114. 19 16
  115. 10 16
  116. 10 11
  117. 14 4
  118. 12 17
  119. 18 1
  120. 9 18
  121. 14 2
  122. 2 12
  123. 19 4
  124. 17 10
  125. 19 7
  126. */
  127.  
Success #stdin #stdout 0.01s 5300KB
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:
1
1
https://ideone.com/XBlbAw
language:
C++ (gcc 8.3)
created:
16 days 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!