fork download
copy 
  1. //============================================================================
  2. // Name : firstTrial.cpp
  3. // Author :
  4. // Version :
  5. // Copyright : Your copyright notice
  6. // Description : Hello World in C++, Ansi-style
  7. //============================================================================
  8.  
  9. #include <bits/stdc++.h>
  10.  
  11. using namespace std;
  12. const int N = 5e5 + 20, MOD = 1e9 + 7;;
  13. int seg[4 * N];
  14. vector<int> adj[N];
  15. int club[N], level[N], ans[N], in[N], out[N], T, add[N], rmove[N], addIdx, removeIdx;
  16. pair<int,pair<int, int> > que[N];
  17. void pre(int n){
  18. 	for(int i = 0; i < n; i++)
  19. 		que[i].second.first = level[que[i].second.second];
  20. 	sort(que, que + n);
  21. }
  22.  
  23. void dfs(int u){
  24. 	in[u] = T++;
  25. 	for(int i = 0; i < (int)adj[u].size(); i++)
  26. 		dfs(adj[u][i]);
  27. 	out[u] = T - 1;
  28. }
  29. void up(int l, int r, int idx, int qidx, int val){
  30. 	if(qidx < l || r < qidx)
  31. 		return;
  32. 	if(l == r){
  33. 		seg[idx] = val;
  34. 		return;
  35. 	}
  36. 	int mid = (l + r) / 2;
  37. 	up(l, mid, idx * 2, qidx, val);
  38. 	up(mid + 1, r, idx * 2 + 1, qidx, val);
  39. 	seg[idx] = (0ll + seg[idx * 2] + seg[idx * 2 + 1]) % MOD;
  40. }
  41. int sum(int l, int r, int idx, int ql, int qr){
  42. 	if(r < ql || qr < l)
  43. 		return 0;
  44. 	if(ql <= l && r <= qr)
  45. 		return seg[idx];
  46. 	int mid = (l + r) / 2;
  47. 	return (0ll + sum(l, mid, idx * 2, ql, qr) + sum(mid + 1, r, idx * 2 + 1, ql, qr)) % MOD;
  48. }
  49. void solve(int n){
  50. 	T = 0;
  51. 	dfs(0);
  52. 	assert(T < 500010);
  53.  
  54. 	addIdx = removeIdx = -1;
  55. 	bool flag;
  56. 	for(int i = 0; i < n; i++){
  57. 		if(i == 0 || (i && que[i].first != que[i - 1].first)){
  58. 			while(removeIdx != -1){
  59. 				int cur = rmove[removeIdx];
  60. 				up(0, T + 1, 1, in[cur], 0);
  61. 				removeIdx--;
  62. 			}
  63. 			addIdx = -1;
  64. 			flag = 0;
  65. 		}
  66. 		if(flag){
  67. 			ans[que[i].second.second] = 0;
  68. 			continue;
  69. 		}
  70. 		if((i && que[i].first == que[i - 1].first && (que[i].second.first == que[i - 1].second.first || que[i].second.first - 1 == que[i - 1].second.first))
  71. 				|| (i && que[i].first != que[i - 1].first && que[i].second.first == 0) || (i == 0 && que[i].second.first == 0)){
  72. 			if(i && que[i].first == que[i - 1].first && que[i].second.first != que[i - 1].second.first){
  73. 				while(removeIdx != -1){
  74. 					int cur = rmove[removeIdx];
  75. 					up(0, T + 1, 1, in[cur], 0);
  76. 					removeIdx--;
  77. 				}
  78. 				while(addIdx != -1){
  79. 					int cur = add[addIdx];
  80. 					up(0, T + 1, 1, in[cur], ans[cur]);
  81. 					rmove[++removeIdx] = cur;
  82. 					addIdx--;
  83. 				}
  84. 			}
  85. 			if(que[i].second.first == 0)
  86. 				ans[que[i].second.second] = 1;
  87. 			else
  88. 				ans[que[i].second.second] = sum(0, T + 1, 1, in[que[i].second.second], out[que[i].second.second]);
  89.  
  90. 		}else
  91. 			flag = 1, ans[que[i].second.second] = 0;
  92. 		add[++addIdx] = que[i].second.second;
  93. 	}
  94. 	while(removeIdx != -1){
  95. 		int cur = rmove[removeIdx];
  96. 		up(0, T + 1, 1, in[cur], 0);
  97. 		removeIdx--;
  98. 	}
  99. }
  100.  
  101.  
  102. int main(){
  103. 	int t;
  104. 	scanf("%d", &t);
  105. 	while(t--){
  106. 		memset(adj, 0, sizeof adj);
  107. 		int x, n;
  108. 		scanf("%d%d", &n, &x);
  109. 		for(int i = 1; i < n; i++){
  110. 			int z;
  111. 			scanf("%d", &z);
  112. 			adj[z].push_back(i);
  113. 		}
  114. 		for(int i = 0; i < n; i++){
  115. 			scanf("%d", &club[i]);
  116. 			que[i] = make_pair(club[i], make_pair(-1, i));
  117. 		}
  118. 		for(int i = 0; i < n; i++)
  119. 			scanf("%d", &level[i]);
  120. 		pre(n);
  121. 		solve(n);
  122. 		for(int i = 0; i < n; i++){
  123. 			printf("%d\n", ans[i]);
  124. 		}
  125. 	}
  126. 	return 0;
  127. }
  128.  
Success #stdin #stdout 0s 54312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/s9OWbY
language:
C++14 (gcc 8.3)
created:
6 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!