fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6.  
  7. vector<ll> graph[1001];
  8. vector<ll> depth(1001);
  9. vector<ll> visited(1001);
  10. vector<ll> parent(1001);
  11. ll t, n, cnt;
  12.  
  13. void dfs() {
  14.     //memset(visited, 0, sizeof(visited));
  15.     ll i, j, currDepth = 0;
  16.  
  17.     for(i=1; i<=n; i++) {
  18.         for(auto j : graph[i]) {
  19.             if(visited[j] == 0) {
  20.                 depth[j] = currDepth;
  21.                 visited[j] = 1;
  22.                 parent[j] = i;
  23.             }
  24.         }
  25.         currDepth++;
  26.     }
  27. }
  28.  
  29. ll lca(ll a, ll b) {
  30.  
  31.  
  32.     ll diff = (depth[a] > depth[b]) ? (depth[a]-depth[b]) : (depth[b]-depth[a]); 
  33.  
  34. /*    
  35.     ll x = (depth[a] > depth[b]) ? a : b;
  36.     ll y = (depth[a] > depth[b]) ? b : a;
  37. */
  38.  
  39.     while(diff > 0) {
  40.  
  41.         if(depth[a] > depth[b])
  42.             a = parent[a];
  43.         else if(depth[a] < depth[b])
  44.             b = parent[b];
  45.         diff--;
  46.     }
  47.     if(a == b)
  48.         return a;
  49.  
  50.     while(parent[a] != parent[b]) {
  51.         a = parent[a];
  52.         b = parent[b];
  53.     }
  54.     return parent[a];
  55. }
  56.  
  57. void solve() {
  58. 	ll m, q, i, j, x, y;
  59.  
  60. 	cin >> n;
  61.  
  62. 	for(i=1; i<=n; i++) {
  63. 		cin >> m;
  64. 		for(j=0; j<m; j++) {
  65. 			cin >> x;
  66. 			graph[i].push_back(x);
  67. 		}
  68. 	}
  69.  
  70. 	cin >> q;
  71.  
  72. 	dfs();
  73. 	parent[1] = 1;
  74. 	cout << "Case " << (cnt+1) << ":\n";
  75. 	for(i=1; i<=q; i++) {
  76. 		cin >> x >> y;
  77. 		cout << lca(x, y) << endl;
  78. 	}
  79. /*	
  80. 	for(i=1; i<=n; i++) {
  81. 		for(auto j : graph[i]) {
  82. 			cout << j << " ";
  83. 		}
  84. 		cout << "\n";
  85. 	}
  86. */
  87.     /*
  88.     for(i=1; i<=n; i++) {
  89.         cout << parent[i] << " " << depth[i] << endl;
  90.     }
  91.     */
  92. }
  93.  
  94. int main() {
  95.  
  96. 	cin >> t;
  97.  
  98. 	for(cnt=0; cnt<t; cnt++)
  99. 		solve();
  100.  
  101. 	return 0;
  102. }
Success #stdin #stdout 0.01s 5496KB
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/rZEe3k
problem LCA, based on SPOJ submission 28024383 (CPP14), 2021-06-08 06:12:12
language:
C++14 (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!