fork download
  1. /******************************************
  2. * AUTHOR : RAJAGOPALAN *
  3. * NICK : ARNO *
  4. * INSTITUTION : VIT *
  5. ******************************************/
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/detail/standard_policies.hpp>
  8.  
  9. #define ll long long
  10. #define ull unsigned long long
  11. #define pb push_back
  12. #define mp make_pair
  13. #define all(x) (x).begin(), (x).end()
  14. #define alli(a, n, k) (a + k), (a + n + k)
  15. #define FP(i, a, b, k) for (__typeof(a) i = a; i < b; i += k)
  16. #define FS(i, a, b, k) for (__typeof(a) i = a; i > b; i -= k)
  17. #define IT(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  18. #define eps 1e-6
  19. #define pi 3.141592653589793
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template <class T>
  24. inline T gcd(T x, T y)
  25. {
  26. if (!y)
  27. return x;
  28. return gcd(y, x % y);
  29. }
  30. typedef vector<int> VII;
  31. typedef vector<ll> VLL;
  32. typedef pair<int, int> PII;
  33. typedef vector<pair<int, int>> VPII;
  34. typedef vector<pair<int, PII>> VPPI;
  35. const int MOD = 1e9 + 7;
  36. const int INF = 1e9;
  37.  
  38. inline ll modulo(ll a, ll m)
  39. {
  40. return (a % m + m) % m;
  41. }
  42.  
  43. inline ll modInverse(ll a, ll m)
  44. {
  45. assert(__gcd(a, m) == 1);
  46. ll m0 = m;
  47. ll y = 0, x = 1;
  48.  
  49. if (m == 1)
  50. return 0;
  51.  
  52. while (a > 1)
  53. {
  54. ll q = a / m;
  55. ll t = m;
  56.  
  57. m = a % m, a = t;
  58. t = y;
  59.  
  60. y = x - q * y;
  61. x = t;
  62. }
  63.  
  64. if (x < 0)
  65. x += m0;
  66.  
  67. return x;
  68. }
  69.  
  70. inline ll modPow(ll x, ll y, ll m)
  71. { //x^y % m
  72. if (y == 0)
  73. return 1LL;
  74. else if (y == 1)
  75. return x;
  76. else
  77. {
  78. ll ans = modPow(x, y / 2, m) % m;
  79. if (y & 1)
  80. {
  81. return (((ans * ans) % m) * x) % m;
  82. }
  83. else
  84. {
  85. return (ans * ans) % m;
  86. }
  87. }
  88. }
  89. vector<VII> adj(10001);
  90. vector<bool> vis(10001);
  91. vector<int> depth(10001);
  92. unordered_map<int,bool> nR;
  93. int D,n;
  94. void bfs(int r,vector<VII>& par)
  95. {
  96. queue<int> q;
  97. q.push(r);
  98. depth[r]=0;
  99. vis[r]=true;
  100. while(!q.empty())
  101. {
  102. int u=q.front();
  103. q.pop();
  104. for(auto it:adj[u])
  105. if(!vis[it])
  106. {
  107. vis[it]=true;
  108. q.push(it);
  109. depth[it]=depth[u]+1;
  110. par[0][it]=u;
  111. }
  112. }
  113. //cout<<"HERE"<<endl;
  114. }
  115. int walk(int i,int k,vector<VII>& par)
  116. {
  117. for(int d=0;d<=D && i!=-1;++d)
  118. if((1<<d) && k)i=par[d][i];
  119.  
  120. return i;
  121. }
  122. int LCA(int u,int v,vector<VII>& par)
  123. {
  124. if(depth[u]>depth[v])
  125. u=walk(u,depth[u]-depth[v],par);
  126. else if(depth[u]<depth[v])
  127. v=walk(v,depth[v]-depth[u],par);
  128.  
  129. if(u==v)
  130. return u;
  131.  
  132. for(int d=D;d>=0;--d)
  133. {
  134. if(par[d][u]!=par[d][v])
  135. {
  136. u=par[d][u];
  137. v=par[d][v];
  138. }
  139. }
  140. return par[0][u];
  141. }
  142. int main(int argc, char *argv[])
  143. {
  144. ios::sync_with_stdio(false);
  145. cin.tie(NULL);
  146. int t;
  147. cin>>t;
  148. for(int i=1;i<=t;++i)
  149. {
  150. cin>>n;
  151. nR.clear();
  152. for(int i=0;i<n;++i)
  153. {
  154. adj[i].clear();
  155. depth[i]=0;
  156. vis[i]=false;
  157. }
  158. for(int i=1;i<=n;++i)
  159. {
  160. int sz;
  161. cin>>sz;
  162. int sx;
  163. for(int j=0;j<sz;++j)
  164. {
  165. cin>>sx;
  166. adj[i-1].pb(sx-1);
  167. nR[sx-1]=true;
  168. //adj[sx-1].pb(i-1);
  169. }
  170. }
  171. int root;
  172. for(int i=0;i<n;++i)
  173. if(!nR[i]){
  174. root=i;
  175. }
  176. //cout<<"HERE"<<endl;
  177. D=log2(n);
  178. vector<VII> par(D+1,VII(n,-1));
  179. bfs(root,par);
  180. //cout<<"HERE1"<<endl;
  181. for(int i=0;i<n;++i)
  182. {
  183. for(int d=1;d<=D;++d)
  184. {
  185. int mid=par[d-1][i];
  186. if(mid!=-1)
  187. par[d][i]=par[d-1][mid];
  188. }
  189. }
  190. //cout<<"HERE2"<<endl;
  191.  
  192. int q;
  193. cin>>q;
  194. cout<<"Case "<<t<<":\n";
  195. while(q--)
  196. {
  197. int x,y;
  198. cin>>x>>y;
  199. cout<<1+LCA(x-1,y-1,par)<<endl;
  200. }
  201. }
  202. return 0;
  203. }
Success #stdin #stdout 0s 4520KB
stdin
1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7
stdout
Case 1:
3
1