fork download
copy 
  1. /** SPOJ Problem - LCA **/
  2.  
  3. #include <bits/stdc++.h>
  4. #define ll long long
  5. #define pb push_back
  6. #define mod 1000000009
  7. using namespace std;
  8.  
  9. ll n, a, b, q;
  10. vector<ll> tree[1001];
  11. const ll maxN = 20;
  12. ll level[1001], LCA[1001][maxN + 1];  
  13.  
  14. void dfs(ll node, ll lvl, ll par){
  15.     level[node] = lvl;
  16.     LCA[node][0] = par;
  17.  
  18.     for(auto child : tree[node]){
  19.         if(child != par){
  20.             dfs(child, lvl + 1, node);
  21.         }
  22.     }
  23. }
  24.  
  25. void init(ll node){
  26.     for(ll i = 1; i <= n; i++){
  27.         for(ll j = 0; j <= maxN; j++){
  28.             LCA[i][j] = -1;
  29.         }
  30.     }
  31.  
  32.     dfs(1, 0, -1);
  33.  
  34.     for(ll i = 1; i <= maxN; i++){
  35.         for(ll j = 1; j <= node; j++){
  36.             if(LCA[j][i - 1] != -1){
  37.                 ll par = LCA[j][i - 1];
  38.                 LCA[j][i] = LCA[par][i - 1];
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. ll getLCA(ll a, ll b){
  45.     if(level[a] > level[b]) 
  46.         swap(a, b);
  47.     ll d = level[b] - level[a];
  48.  
  49.     while(d > 0){
  50.         ll i = log2(d);
  51.         b = LCA[b][i];
  52.         d -= (1 << i);
  53.     }
  54.  
  55.     if(a == b) 
  56.         return a;
  57.  
  58.     for(ll i = maxN; i >= 0; i--){
  59.         if(LCA[a][i] != -1 && LCA[a][i] != LCA[b][i]){
  60.             a = LCA[a][i];
  61.             b = LCA[b][i];
  62.         }
  63.     }
  64.     return LCA[a][0];
  65. }
  66.  
  67. int main() {
  68.     ios_base :: sync_with_stdio(false);
  69.     cin.tie(NULL);
  70.  
  71.     ll t;
  72.     cin >> t;
  73.     for(ll tc = 1; tc <= t; tc++){
  74.         cout << "Case " << tc << ":\n";
  75.         cin >> n;
  76.         ll m, node;
  77.         for(ll i = 1; i <= n; i++){
  78.             cin >> m;
  79.             for(ll j = 1; j <= m; j++){
  80.                 cin >> node;
  81.                 tree[i].pb(node);
  82.             }
  83.         }
  84.  
  85.         init(n);
  86.  
  87.         cin >> q;
  88.         while(q--){
  89.             cin >> a >> b;
  90.             cout << getLCA(a, b) << "\n";
  91.         }
  92.     }
  93.     return 0;
  94. }
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
https://ideone.com/2cjrN6
language:
C++14 (gcc 8.3)
created:
3 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!