fork download
copy 
  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
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:
3
1
https://ideone.com/wHCmTn
problem LCA, based on SPOJ submission 25555860 (CPP14), 2020-03-16 14:26:21
language:
C++14 (gcc 8.3)
created:
4 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!