YEZAELP

SPOJ: Lowest Common Ancestor

Nov 30th, 2021
612
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e3;
  5. const int logN = log2(N);
  6. vector <int> g[N];
  7. int rnk[N + 10], par[N + 10][logN + 10];
  8. bool vs[N + 10];
  9. void Setting();
  10.  
  11. void dfs(int u, int p, int d){
  12.     if(vs[u]) return;
  13.     par[u][0] = p;
  14.     rnk[u] = d;
  15.     for(auto v: g[u]){
  16.         if(v != p) dfs(v, u, d + 1);
  17.     }
  18. }
  19.  
  20. int LCA(int u, int v){
  21.     if(rnk[u] < rnk[v]) /// u -> v
  22.         swap(u, v);
  23.     for(int e=logN;e>=0;e--){ /// [2 ^ logN, 2^0]
  24.         if(rnk[par[u][e]] >= rnk[v]){
  25.             u = par[u][e];
  26.         }
  27.     }
  28.     if(u == v) return u;
  29.     for(int e=logN;e>=0;e--){ /// [2 ^ logN, 2^0]
  30.         if(par[u][e] != par[v][e]){
  31.             u = par[u][e];
  32.             v = par[v][e];
  33.         }
  34.     }
  35.     return par[u][0];
  36. }
  37.  
  38. void Solve(){
  39.     int n; scanf("%d", &n);
  40.     for(int u=1;u<=n;u++){
  41.         int node;
  42.         scanf("%d", &node);
  43.         for(int j=1;j<=node;j++){
  44.             int v; scanf("%d", &v);
  45.             g[u].push_back(v);
  46.             g[v].push_back(u);
  47.         }
  48.     }
  49.     dfs(1, 0, 1);
  50.     for(int e=1;e<=logN;e++){
  51.         for(int u=1;u<=n;u++){
  52.             par[u][e] = par[par[u][e - 1]][e - 1];
  53.         }
  54.     }
  55.     int Q; scanf("%d", &Q);
  56.     for(int q=1;q<=Q;q++){
  57.         int u, v; scanf("%d %d", &u, &v);
  58.         printf("%d\n", LCA(u, v));
  59.     }
  60. }
  61.  
  62. int main(){
  63.  
  64.     int T; scanf("%d", &T);
  65.  
  66.     for(int t=1;t<=T;t++){
  67.         printf("Case %d:\n", t);
  68.         Solve();
  69.         Setting();
  70.     }
  71.  
  72.     return 0;
  73. }
  74.  
  75. void Setting(){
  76.     for(int u=0;u<=N;u++){
  77.         rnk[u] = 0;
  78.         vs[u] = false;
  79.         if(!g[u].empty()) g[u].clear();
  80.         for(int e=0;e<=logN;e++){
  81.             par[u][e] = 0;
  82.         }
  83.     }
  84. }
RAW Paste Data