fork download
copy 
  1.  
  2. // ~/BAU/ACM-ICPC/Teams/A++/BlackBurn95
  3. // ~/sudo apt-get Accpeted
  4.  
  5. #include <iostream>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <time.h>
  9. #include <memory.h>
  10. #include <limits.h>
  11. #include <math.h>
  12. #include <string.h>
  13. #include <string>
  14. #include <algorithm>
  15. #include <vector>
  16. #include <queue>
  17. #include <stack>
  18. #include <set>
  19. #include <map>
  20. #include <unordered_set>
  21. #include <unordered_map>
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef unsigned long long ull;
  27.  
  28. const int N = 100000;
  29. const int l = 16;
  30. int n, dpth[N], dp[l + 1][N];
  31. vector<vector<int> > g;
  32.  
  33. void dfs(int u, int p) {
  34. 	dp[0][u] = p;
  35.  
  36. 	for(int i=0; i<g[u].size(); i++)
  37. 		if (g[u][i] != p) {
  38. 			dpth[g[u][i]] = dpth[u] + 1;
  39. 			dfs(g[u][i], u);
  40. 		}
  41. }
  42.  
  43. int getKthAncestor(int u, int k) {
  44. 	int d = dpth[u] - k;
  45.  
  46. 	for (int j = l; j >= 0; j--) {
  47. 		int nu = dp[j][u];
  48. 		if (nu == -1) continue;
  49. 		if (dpth[nu] == d) return nu;
  50. 		else if (dpth[nu] > d) u = nu;
  51. 	}
  52.  
  53. 	return -1;
  54. }
  55.  
  56. int getLCA(int a, int b) {
  57. 	if (dpth[a] > dpth[b]) a = getKthAncestor(a, dpth[a] - dpth[b]);
  58. 	else if (dpth[b] > dpth[a]) b = getKthAncestor(b, dpth[b] - dpth[a]);
  59.  
  60. 	//dpth[a] == dpth[b]
  61.  
  62. 	if (a == b) return a;
  63.  
  64. 	for (int j = l; j >= 0; j--) {
  65. 		int na = dp[j][a], nb = dp[j][b];
  66.  
  67. 		if (na != -1 && nb != -1 && na != nb)
  68. 			a = na, b = nb;
  69. 	}
  70.  
  71. 	return dp[0][a];
  72. }
  73.  
  74. int main() {
  75. 	int tc;
  76. 	scanf("%d", &tc);
  77.  
  78. 	for (int c = 1; c <= tc; c++) {
  79. 		scanf("%d", &n);
  80.  
  81. 		g.clear();
  82. 		g.resize(n);
  83.  
  84. 		for (int i = 0; i < n; i++) {
  85. 			int m, j;
  86. 			scanf("%d", &m);
  87. 			while (m--) {
  88. 				scanf("%d", &j);
  89. 				j--;
  90. 				g[i].push_back(j);
  91. 				g[j].push_back(i);
  92. 			}
  93. 		}
  94.  
  95. 		memset(dp, -1, sizeof(dp));
  96.  
  97. 		dpth[0] = 0;
  98. 		dfs(0, -1);
  99.  
  100. 		for (int j = 1; j <= l; j++)
  101. 			for (int i = 0; i < n; i++)
  102. 				dp[j][i] = (dp[j - 1][i] == -1 ? -1 : dp[j - 1][dp[j - 1][i]]);
  103.  
  104. 		printf("Case %d:\n", c);
  105. 		int q;
  106. 		scanf("%d", &q);
  107. 		while (q--) {
  108. 			int a, b;
  109. 			scanf("%d%d", &a, &b);
  110. 			a--, b--;
  111.  
  112. 			printf("%d\n", getLCA(a, b) + 1);
  113. 		}
  114. 	}
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 22256KB
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/ZPwQ1K
language:
C++14 (gcc 8.3)
created:
8 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!