fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. vector<int> tin, tout;
  7. vector<pair<vector<int>, int>> g;
  8. vector<vector<int>> up;
  9. int l;
  10.  
  11. int t;
  12. void dfs(int v, int p) {
  13. 	tin[v] = t++;
  14. 	up[v][0] = p;
  15. 	for (int i = 1; i <= l; ++i)
  16. 		up[v][i] = up[up[v][i - 1]][i - 1];
  17. 	for(int i = 0; i < g[v].first.size(); ++i)
  18. 		dfs(g[v].first[i], v);
  19. 	tout[v] = t++;
  20. }
  21.  
  22.  
  23. int lca (int a, int b) {
  24. 	if (tin[a] <= tin[b] && tout[a] >= tout[b]) return a;
  25. 	if (tin[a] >= tin[b] && tout[a] <= tout[b]) return b;
  26.  
  27. 	for (int i = l; i >= 0; --i)
  28. 		if (tin[up[a][i]] < tin[b] && tout[up[a][i]] > tout[b])
  29. 			a = up[a][i];
  30. 	return up[a][0];
  31. }
  32.  
  33.  
  34. int main() {
  35. 	int n, h, v; cin >> n;
  36. 	l = log2(n * 2 - 1);
  37. 	tin.resize(n);
  38. 	tout.resize(n);
  39. 	g.resize(n); up.resize(n, vector <int> (l));
  40. 	for(int i = 0; i < n; ++i) {
  41. 		cin >> h;
  42. 		if(h != 0)
  43. 			g[h - 1].first.push_back(i);
  44. 		else
  45. 			v = i;
  46. 	}
  47. 	dfs(v, 0);
  48.  
  49. 	cin >> n;
  50. 	for(int i = 0; i < n; ++i) {
  51.  
  52. 	}
  53. 	return 0;
  54. }
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
0 1
1
2 1
stdout
copy 
Standard output is empty
https://ideone.com/sJoINY
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!