fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6. " when you are not practicing someone else is ,
  7.  and the day u meet them u will lose "
  8.  
  9. */
  10. #include<bits/stdc++.h>
  11. #include<stdio.h>
  12. using namespace std;
  13.  
  14. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define MAX 1050
  16.  
  17. #define ll long long
  18. #define ld long double
  19. #define lli long long int
  20.  
  21. #define pb push_back
  22. #define INF 1000000000000
  23. #define mod 1000000007
  24.  
  25. // trignometric function always give value in Radians only
  26. #define PI acos(-1) //3.1415926535897932384626433832795028
  27. #define dsin(degree) sin(degree*(PI/180.0))
  28. #define dcos(degree) cos(degree*(PI/180.0))
  29. #define dtan(degree) tan(degree*(PI/180.0))
  30.  
  31. #define rsin(radian) sin(radian)
  32. #define rcos(radian) cos(radian)
  33. #define rtan(radian) tan(radian)
  34.  
  35. #define mem0(a) memset(a,0,sizeof(a))
  36. #define mem1(a) memset(a,-1,sizeof(a))
  37.  
  38. #define loop(i,n) for (lli i = 0; i < n; i++)
  39. #define FOR(i,a,b) for (lli i = a; i < b; i+=1)
  40.  
  41. #define all(v) v.begin(),v.end()
  42. #define rall(v) v.rbegin(),v.rend()
  43. #define sz(x) int(x.size())
  44. #define F first
  45. #define S second
  46.  
  47. #define mii map<lli,lli>
  48. #define mci map<char,lli>
  49. #define vi vector<lli>
  50. #define vbool vector<bool>
  51. #define seti set<lli>
  52. #define pii pair<lli,lli>
  53. #define pcc pair<char,char>
  54.  
  55. #define gcd(a,b) __gcd((a),(b))
  56. #define lcm(a,b) (a/gcd(a,b))*b
  57. #define abs(x) ((x < 0)?-(x):x)
  58.  
  59. #define endl '\n'
  60.  
  61. template <typename T>
  62. void print(T x){cout<<x<<endl;}
  63. template <typename T1, typename T2>
  64. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  65. template <typename T1, typename T2,typename T3>
  66. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  67.  
  68. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  69. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  70.  
  71. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  72. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  73.  
  74. #define FD(N) fixed<<setprecision(N)
  75.  
  76. #define deb(x) cout<<#x<<" "<<x<<endl;
  77.  
  78. // chandan1,2
  79. void chandan1(){int y=1;return;}
  80. void chandan2(){
  81.         loop(i,10){
  82.         lli x=1;
  83.     }
  84.     return(chandan1());
  85. }
  86.  
  87. //--------------------------------------------------------------------------------------------------------------------------------------------
  88. // LCA -
  89. #define maxN 21
  90.  
  91. vi adj[MAX];
  92. vbool vis(MAX,0);
  93. lli level[MAX];
  94. lli LCA[MAX][maxN];
  95.  
  96. void dfs(lli src , lli lvl , lli parent)
  97. {
  98.     level[src] = lvl;
  99.     LCA[src][0] = parent;
  100.  
  101.     for(auto child : adj[src])
  102.     {
  103.         if(child != parent)
  104.             dfs(child , lvl+1 , src);
  105.     }
  106. }
  107.  
  108.  
  109. void preprocess(lli N)
  110. {
  111.     dfs(1,0,-1);
  112.  
  113.     for(lli i = 1; i<maxN ; i++)
  114. 	{
  115. 		for(lli j = 1 ; j <= N;j++)
  116. 		{
  117. 		    if(LCA[j][i-1] != -1)
  118.     		{
  119.     			lli parent = LCA[j][i-1];
  120.     			LCA[j][i] = LCA[parent][i-1];
  121.     		}
  122. 		}
  123. 	}
  124. }
  125.  
  126. lli getLCA(lli a , lli b)
  127. {
  128. 	if(level[b] < level[a])
  129. 	    swap(a , b);
  130.  
  131. 	lli dist = level[b] - level[a];
  132.  
  133. 	while(dist)
  134. 	{
  135. 		lli i = log2(dist);
  136.  
  137. 		b = LCA[b][i];
  138.  
  139. 		dist -= (1<<i);
  140. 	}
  141.  
  142. 	if(a == b)
  143. 	    return a;
  144.  
  145. 	for(lli i=maxN-1;i>=0;i--)
  146. 	{
  147. 	    if(LCA[a][i] != -1 and (LCA[a][i] != LCA[b][i]) )
  148. 	    {
  149. 	        a = LCA[a][i];
  150. 	        b = LCA[b][i];
  151. 	    }
  152. 	}
  153.  
  154. 	return LCA[a][0];
  155. }
  156.  
  157. lli getDistance(lli a , lli b)
  158. {
  159. 	lli lca = getLCA(a , b);
  160.  
  161. 	return (level[a] + level[b] - 2*level[lca]);
  162. }
  163.  
  164. //--------------------------------------------------------------------------------------------------------------------------------------------
  165.  
  166.  
  167. int main(){
  168. fastio
  169. lli t=1;
  170. cin>>t;
  171. chandan2();
  172. loop(qw,t) {
  173.     lli n;
  174.     cin>>n;
  175.  
  176.     mem1(LCA);
  177.     mem0(level);
  178.     loop(i,MAX) adj[i].clear();
  179.  
  180.     loop(i,n)
  181.     {
  182.         lli num;
  183.         cin>>num;
  184.         while(num--){
  185.             lli x;
  186.             cin>>x;
  187.             adj[i+1].pb(x);
  188.         }
  189.     }
  190.  
  191.     preprocess(n);
  192.  
  193.     lli q;
  194.     cin>>q;
  195.     cout<<"Case "<<qw+1<<":\n";
  196.  
  197.     while(q--)
  198.     {
  199.  
  200.         lli a , b;
  201.         cin>>a>>b;
  202.  
  203.         print(getLCA(a , b));
  204.  
  205.     }
  206.  
  207.  
  208.   }
  209. return 0;
  210. }
Success #stdin #stdout 0.01s 5340KB
comments (?)
stdin
copy 
2

7
3 2 3 4
0
3 5 6 7
0
0
0
0
5
5 7
2 7
3 5
1 7
4 7

6
2 2 3
1 4
2 5 6
0
0
0
3
1 4
3 4
5 2
stdout
copy 
Case 1:
3
1
3
1
1
Case 2:
1
1
1
https://ideone.com/K025nA
language:
C++ (gcc 8.3)
created:
4 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!