fork(1) download 
  1.  
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int loc[1000000], ans[1000000], size[1000000], queue[1000000];
  9. vector<int> son[1000000], unknown[1000000];
  10. pair<int, int> stack[1000000];
  11.  
  12. int main() {
  13. 	int n, root;
  14. 	scanf("%d", &n);
  15. 	for (int i = 0; i < n; i ++) loc[i] = ans[i] = -1;
  16. 	for (int i = 0; i < n; i ++) {
  17. 		int a, b;
  18. 		scanf("%d%d", &a, &b);
  19. 		a --;
  20. 		b --;
  21. 		if (a == i) {
  22. 			root = i;
  23. 			continue;
  24. 		}
  25. 		son[a].push_back(i);
  26. 		if (b >= 0) {
  27. 			ans[i] = b;
  28. 			loc[b] = i;
  29. 		} else {
  30. 			unknown[a].push_back(i);
  31. 		}
  32. 	}
  33. 	ans[root] = n - 1;
  34. 	loc[n-1] = root;
  35.  
  36. 	queue[0] = root;
  37. 	for (int head = 0, tail = 1; head < tail; head ++)
  38. 		for (int i = 0; i < son[queue[head]].size(); i ++)
  39. 			queue[tail ++] = son[queue[head]][i];
  40. 	for (int i = n - 1; i >= 0; i --) {
  41. 		size[queue[i]] = 1;
  42. 		for (int j = 0; j < son[queue[i]].size(); j ++)
  43. 			size[queue[i]] += size[son[queue[i]][j]];
  44. 	}
  45.  
  46. 	int top = 0;
  47. 	for (int i = 0; i < n; i ++) {
  48. 		if (loc[i] == -1) {
  49. 			int x = (top > 0) ? stack[top - 1].second : 0;
  50. 			stack[top ++] = make_pair(i, x);
  51. 			continue;
  52. 		}
  53. 		int sum = 0;
  54. 		for (int j = 0; j < unknown[loc[i]].size(); j ++)
  55. 			sum += size[unknown[loc[i]][j]];
  56. 		int now = top - 1;
  57. 		for (int j = sum; j > 0; j --)
  58. 			stack[now --].second += j;
  59. 		now = loc[i];
  60. 		while (unknown[now].size() == 1) {
  61. 			int x = unknown[now][0];
  62. 			if (top == 1 || stack[top - 2].second == top - 1) {
  63. 				ans[x] = stack[-- top].first;
  64. 				now = x;
  65. 			} else {
  66. 				break;
  67. 			}
  68. 		}
  69. 	}
  70.  
  71. 	for (int i = 0; i < n; i ++)
  72. 		printf("%d\n", ans[i] + 1);
  73.  
  74. 	return 0;
  75. }
  76.  
Success #stdin #stdout 0.05s 49736KB
comments (?)
stdin 
10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0
stdout 
2
10
1
9
5
8
0
0
0
0
https://ideone.com/mPQl6
language:
C++ (gcc 8.3)
created:
14 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!