fork download
copy 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. #ifdef DONLINE_JUDGE
  35. 	// palindromic tree is better than splay tree!
  36. 	#define lld I64d
  37. #endif
  38.  
  39. int N, Pp =0;
  40. vector<int> P,path,S;
  41.  
  42. struct fin {
  43. 	vector<int> T;
  44. 	fin() {}
  45. 	fin(int N) {T.resize(N+10,0);}
  46.  
  47. 	int lastone(int x) {return x&(x^(x-1));}
  48.  
  49. 	void put(int pos) {
  50. 		for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i]++;}
  51.  
  52. 	int get(int pos) {
  53. 		int ret =0;
  54. 		for(int i =pos+1; i > 0; i -=lastone(i)) ret +=T[i];
  55. 		return ret;}
  56. 	};
  57.  
  58. vector<fin> Fp;
  59. vector< map<int,int> > Sp;
  60.  
  61. void prep(int R, vector< vector<int> > &son) {
  62. 	int topson =-1;
  63. 	ALL_THE(son[R],it) {
  64. 		prep(*it,son);
  65. 		S[R] +=S[*it];
  66. 		if(topson == -1 || S[*it] > S[topson]) topson =*it;
  67. 		}
  68. 	if(topson == -1) {
  69. 		path[R] =Pp;
  70. 		Pp++;}
  71. 	else path[R] =path[topson];
  72. 	ALL_THE(son[R],it) if(*it != topson) 
  73. 		ALL_THE(Sp[path[*it]],jt) Sp[path[R]][jt->ff] =0;
  74. 	Sp[path[R]][P[R]] =0;}
  75.  
  76. int count_brute(int R, vector< vector<int> > &son, int val, vector<int> &listP) {
  77. 	int ans =0;
  78. 	ALL_THE(son[R],it) 
  79. 		ans +=count_brute(*it,son,val,listP);
  80. 	listP.push_back(P[R]);
  81. 	if(P[R] > val) ans++;
  82. 	return ans;}
  83.  
  84. vector<int> ans;
  85.  
  86. void count(int R, vector< vector<int> > &son) {
  87. 	vector<int> listP;
  88. 	ALL_THE(son[R],it) {
  89. 		count(*it,son);
  90. 		if(path[*it] != path[R]) ans[R] +=count_brute(*it,son,P[R],listP);
  91. 		else ans[R] +=S[*it]-Fp[path[R]].get(Sp[path[R]][P[R]]);}
  92. 	ALL_THE(listP,it) Fp[path[R]].put(Sp[path[R]][*it]);
  93. 	Fp[path[R]].put(Sp[path[R]][P[R]]);}
  94.  
  95. int main() {
  96. 	cin.sync_with_stdio(0);
  97. 	cin.tie(0);
  98. 	cout << fixed << setprecision(10);
  99. #ifndef LOCAL
  100. 	freopen("promote.in","r",stdin);
  101. 	freopen("promote.out","w",stdout);
  102. #endif
  103. 	int N;
  104. 	cin >> N;
  105. 	P.resize(N);
  106. 	Fp.resize(N);
  107. 	Sp.resize(N);
  108. 	for(int i =0; i < N; i++) cin >> P[i];
  109. 	path.resize(N,-1);
  110. 	S.resize(N,1);
  111. 	vector< vector<int> > son(N);
  112. 	for(int i =1; i < N; i++) {
  113. 		int p;
  114. 		cin >> p;
  115. 		son[p-1].push_back(i);}
  116. 	prep(0,son);
  117. 	for(int i =0; i < Pp; i++) {
  118. 		int x =0;
  119. 		ALL_THE(Sp[i],it) it->ss =x++;
  120. 		Fp[i] =fin(x);}
  121. 	ans.resize(N,0);
  122. 	count(0,son);
  123. 	for(int i =0; i < N; i++) cout << ans[i] << "\n";
  124. 	return 0;}
  125.  
  126. // look at my code
  127. // my code is amazing
  128.  
Runtime error #stdin #stdout #stderr 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/LXdvUN
USACO 2017 Jan Platinum, problem 1
language:
C++14 (gcc 8.3)
created:
7 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!