fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef vector<ll> vl;
  7.  
  8. #define INF (int)1e9
  9.  
  10. int n, father[10005], depth[10005], dp[10005][20];
  11. vector<int> child[10005];
  12.  
  13. void dfs(int cur, int par, int dep){
  14. 	father[cur] = par;
  15. 	depth[cur] = dep;
  16. 	for(int i = 0; i < child[cur].size(); i++){
  17. 		int next = child[cur][i];
  18. 		dfs(next, cur, dep+1);
  19. 	}
  20. }
  21.  
  22. void precompute(){
  23. 	for(int i = 0; i < 10005; i++){
  24. 		for(int j = 0; j < 20; j++){
  25. 			dp[i][j] = 1;
  26. 		}
  27. 	}
  28. 	for(int i = 1; i <= n; i++){
  29. 		dp[i][0] = father[i];
  30. 	}
  31. 	for(int p = 1; p <= 15; p++){
  32. 		for(int cur = 1; cur <= n; cur++){
  33. 			dp[cur][p] = dp[dp[cur][p-1]][p-1];
  34. 		}
  35. 	}
  36. }
  37.  
  38. int lca(int a, int b){
  39. 	if(depth[a] > depth[b]){
  40. 		swap(a, b);
  41. 	}
  42. 	int dif = depth[b] - depth[a];
  43. 	for(int p = 15; p >= 0; p--){
  44. 		if( (1 << p) <= dif ){
  45. 			b = dp[b][p];
  46. 			dif -= (1 << p);
  47. 		}
  48. 	}
  49. 	if(a == b){
  50. 		return a;
  51. 	}
  52. 	for(int p = 15; p >= 0; p--){	
  53. 		if( dp[b][p] != dp[a][p] ){
  54. 			a = dp[a][p];
  55. 			b = dp[b][p];
  56. 		}
  57. 	}
  58. 	return father[a];
  59. }
  60.  
  61. int main(){
  62. 	int t;
  63. 	cin >> t;
  64. 	for(int test = 1; test <= t; test++){
  65. 		cout << "Case " << t << ":" << endl;
  66. 		cin >> n;
  67. 		int m, temp;
  68. 		for(int i = 1; i <= n; i++){
  69. 			cin >> m;
  70. 			for(int j = 1; j <= m; j++){
  71. 				cin >> temp;
  72. 				child[i].push_back(temp);
  73. 			}
  74. 		}
  75. 		dfs(1, 1, 0);
  76. 		precompute();
  77.  
  78. 		int q, a, b;
  79. 		cin >> q;
  80. 		for(int i = 1; i <= q; i++){
  81. 			cin >> a >> b;
  82. 			cout << lca(a, b) << endl;
  83. 		}
  84. 		for(int i = 1; i <= n; i++){
  85. 			child[i].clear();
  86. 			father[i] = 0;
  87. 			depth[i] = 0;
  88. 		}
  89.  
  90. 	}
  91. }
Success #stdin #stdout 0s 4696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
https://ideone.com/C0qYWk
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!