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. //stack<int> st[N];
  15. vector<int> adj[N], newAdj[2 * N];
  16. int club[N], level[N], root[N], ans[N], in[N], out[N], T, cur[N], last[N], add[N], rmove[N], addIdx, removeIdx;
  17. pair<int,pair<int, int> > que[N];
  18. inline void CLEAR(){
  19. 	memset(newAdj, 0, sizeof newAdj);
  20. 	memset(adj, 0, sizeof adj);
  21. }
  22. inline void dfs(int u){
  23. 	newAdj[cur[club[u]]].push_back(u);
  24. 	last[u] = cur[club[u]];
  25. 	cur[club[u]] = u;
  26. 	for(int i = 0; i < (int)adj[u].size(); i++)
  27. 		dfs(adj[u][i]);
  28. 	cur[club[u]] = last[u];
  29.  
  30. }
  31. inline void simplifyTheTree(int n){
  32. 	for(int i = 0; i < n; i++)
  33. 		root[i] = n + i, cur[i] = n + i;// st[i].push(n + i);
  34. 	dfs(0);
  35. //	for(int i = 0; i < n; i++)
  36. //		st[i].pop();
  37.  
  38. }
  39. inline void pre(int n){
  40. 	for(int i = 0; i < n; i++)
  41. 			que[i].second.first = level[que[i].second.second];
  42.  
  43. 	sort(que, que + n);
  44. }
  45.  
  46. inline void DFS(int u){
  47. 	in[u] = T++;
  48. 	for(int i = 0; i < (int)newAdj[u].size(); i++)
  49. 		DFS(newAdj[u][i]);
  50. 	out[u] = T - 1;
  51. }
  52. inline void up(int l, int r, int idx, int qidx, int val){
  53. 	if(qidx < l || r < qidx)
  54. 		return;
  55. 	if(l == r){
  56. 		seg[idx] = val;
  57. 		return;
  58. 	}
  59. 	int mid = (l + r) / 2;
  60. 	up(l, mid, idx * 2, qidx, val);
  61. 	up(mid + 1, r, idx * 2 + 1, qidx, val);
  62. 	seg[idx] = (0ll + seg[idx * 2] + seg[idx * 2 + 1]) % MOD;
  63. }
  64. inline int sum(int l, int r, int idx, int ql, int qr){
  65. 	if(r < ql || qr < l)
  66. 		return 0;
  67. 	if(ql <= l && r <= qr)
  68. 		return seg[idx];
  69. 	int mid = (l + r) / 2;
  70. 	return (0ll + sum(l, mid, idx * 2, ql, qr) + sum(mid + 1, r, idx * 2 + 1, ql, qr)) % MOD;
  71. }
  72. inline void solve(int n){
  73. 	addIdx = removeIdx = -1;
  74. 	bool flag;
  75. 	for(int i = 0; i < n; i++){
  76. 		if(i == 0 || (i && que[i].first != que[i - 1].first)){
  77. 	//		while(!rmove.empty()){
  78. 	//			int cur = rmove.top();
  79. 	//			up(0, 500010, 1, in[cur], 0);
  80. 	//			rmove.pop();
  81. 	//		}
  82. 			while(removeIdx != -1){
  83. 				int cur = rmove[removeIdx];
  84. 				up(0, 500010, 1, in[cur], 0);
  85. 				removeIdx--;
  86. 			}
  87. 	//		while(!add.empty())add.pop();
  88. 			addIdx = -1;
  89. 			T = 0;
  90. 			DFS(root[club[que[i].second.second]]);
  91. 			flag = 0;
  92. 		}
  93. 		if(flag){
  94. 			ans[que[i].second.second] = 0;
  95. 			continue;
  96. 		}
  97. 		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))
  98. 				|| (i && que[i].first != que[i - 1].first && que[i].second.first == 0) || (i == 0 && que[i].second.first == 0)){
  99. 			if(i && que[i].first == que[i - 1].first && que[i].second.first != que[i - 1].second.first){
  100. //						while(!rmove.empty()){
  101. //							int cur = rmove.top();
  102. ////							cout << "rmove : " << cur << endl;
  103. //							up(0, 500010, 1, in[cur], 0);
  104. //							rmove.pop();
  105. //						}
  106. //						while(!add.empty()){
  107. //							//add have indces
  108. //							int cur = add.top();
  109. ////							cout << "Add :" << cur << ' ' << ans[cur] << endl;
  110. //							up(0, 500010, 1, in[cur], ans[cur]);
  111. //							rmove.push(cur);
  112. //							add.pop();
  113. //						}
  114. 				while(removeIdx != -1){
  115. 					int cur = rmove[removeIdx];
  116. 					up(0, 500010, 1, in[cur], 0);
  117. 					removeIdx--;
  118. 				}
  119. 				while(addIdx != -1){
  120. 					int cur = add[addIdx];
  121. 					up(0, 500010, 1, in[cur], ans[cur]);
  122. 					rmove[++removeIdx] = cur;
  123. 					addIdx--;
  124. 				}
  125. 			}
  126. //				cout << "Get answer to " << que[i][j].second << endl;
  127. 			if(que[i].second.first == 0)
  128. 				ans[que[i].second.second] = 1;
  129. 			else
  130. 				ans[que[i].second.second] = sum(0, 500010, 1, in[que[i].second.second], out[que[i].second.second]);
  131.  
  132. 		}else
  133. 			flag = 1, ans[que[i].second.second] = 0;
  134. //			add.push(que[i][j].second);
  135. 		add[++addIdx] = que[i].second.second;
  136.  
  137. 	}
  138. 	while(removeIdx != -1){
  139. 		int cur = rmove[removeIdx];
  140. 		up(0, 500010, 1, in[cur], 0);
  141. 		removeIdx--;
  142. 	}
  143. }
  144.  
  145.  
  146. int main(){
  147. 	int t;
  148. 	scanf("%d", &t);
  149. 	while(t--){
  150. 		CLEAR();
  151. 		int x, n;
  152. 		scanf("%d%d", &n, &x);
  153. 		for(int i = 1; i < n; i++){
  154. 			int z;
  155. 			scanf("%d", &z);
  156. 			adj[z].push_back(i);
  157. 		}
  158. 		for(int i = 0; i < n; i++){
  159. 			scanf("%d", &club[i]);
  160. 			que[i] = make_pair(club[i], make_pair(-1, i));
  161. 		}
  162. 		for(int i = 0; i < n; i++)
  163. 			scanf("%d", &level[i]);
  164. 		pre(n);//O(n)
  165. 		simplifyTheTree(n);//O(2 * n)
  166.  
  167. 		solve(n);
  168. 		for(int i = 0; i < n; i++){
  169. 			printf("%d\n", ans[i]);
  170. 		}
  171. 	}
  172. 	return 0;
  173. }
  174.  
Runtime error #stdin #stdout 0s 83648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UpAy43
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!