fork download
copy 
  1. //gm  --- akezhon
  2. #include <bits/stdc++.h>
  3. //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
  4. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  5. #define int long long
  6. #define pb push_back
  7. #define F first
  8. #define S second
  9. #define all(v) v.begin(),v.end()
  10. #define pii pair<int,int>
  11. #define tm (tl+tr)/2
  12. #define TL v+v, tl, tm
  13. #define TR v+v+1, tm+1, tr
  14. #define DA l <= tl && tr <= r
  15. #define NET r < tl || tr < l
  16. #define double long double
  17. using namespace std;
  18. const int N=1e5+7;
  19. const int M=1e9+7;
  20. const int inf=1e9;
  21. vector <int> g[N];
  22. vector <pii> query[N];
  23. int up[N][20];
  24. int ans[N];
  25. int d[N];
  26. int sz[N];
  27. int n, q;
  28. void calc(int v, int f){
  29. 	d[v] = f;
  30. 	sz[v] = 1;
  31. 	for(int u : g[v]){
  32. 		calc(u, f+1);
  33. 		sz[v] += sz[u];	
  34. 	}
  35. }
  36. int cnt[N];
  37. void lol(int v, int f){
  38. 	cnt[d[v]] += f;
  39. 	for(int u : g[v])lol(u, f);
  40. }
  41. void dfs(int v, bool cl){
  42. 	int mx=0;
  43. 	for(int u : g[v])if(sz[mx] < sz[u])mx = u;
  44. 	for(int u : g[v])if(mx != u)dfs(u, 1);
  45. 	if(mx)dfs(mx, 0);
  46. 	for(int u : g[v])if(mx != u)lol(u, 1);
  47. 	cnt[d[v]] ++;
  48. 	for(auto [x, y] : query[v])ans[y] = cnt[d[x]]-1;
  49. 	if(cl)lol(v, -1);
  50. }
  51. void AlemAmenov(){
  52.  
  53. 	cin >> n;
  54. 	for(int i=1; i <= n; i++){
  55. 		cin >> up[i][0];
  56. 		if(up[i][0])g[up[i][0]].pb(i);
  57. 	}
  58. 	for(int i=1; i <= 19; i++){
  59. 		for(int j=1; j <= n; j++)up[j][i] = up[up[j][i-1]][i-1];
  60. 	}
  61. 	cin >> q;
  62. 	for(int i=1; i <= q; i++){
  63. 		int v, p, x;
  64. 		cin >> v >> p;
  65. 		x=v;
  66. 		for(int i=0; i <= 19; i++)if((1<<i) & p) v = up[v][i];
  67. 		if(v == 0){
  68. 			ans[i] = 0;
  69. 		}
  70. 		else {
  71. 			query[v].pb({x, i});
  72. 		}
  73. 	}
  74. 	for(int i=1; i <= n; i++){
  75. 		if(!d[i]){
  76. 			calc(i, 1);
  77. 			dfs(i, 1);
  78. 		}
  79. 	}
  80. 	for(int i=1; i <= q; i++){
  81. 		cout << ans[i] << ' ';
  82. 	}
  83. }
  84. signed main(){
  85.  
  86. 	ios_base::sync_with_stdio(0);
  87. 	cin.tie(0);
  88.  
  89. //	freopen("justforfood.in", "r", stdin);
  90. //	freopen("justforfood.out", "w", stdout);
  91. 	int RealName=1;
  92. //	cin >> RealName;
  93. //	int C=0;
  94. 	while(RealName--){
  95. //		cout << "Case " << ++C << ":\n";
  96. 		AlemAmenov();
  97. 	}
  98.  
  99. return 0;
  100. }
Success #stdin #stdout 0.01s 9244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2Qp8z4
language:
C++14 (gcc 8.3)
created:
1 day 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!