fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(x) begin(x), end(x)
  6.  
  7. const int maxn = 2e5 + 42;
  8.  
  9. int64_t ad[4 * maxn];
  10. int64_t sm[4 * maxn];
  11. int64_t px[4 * maxn];
  12.  
  13. void push(int v, int l, int r) {
  14. 	sm[v] += px[v] * ad[v];
  15. 	if(r - l > 1) {
  16. 		px[2 * v] += px[v];
  17. 		px[2 * v + 1] += px[v];
  18. 	}
  19. 	px[v] = 0;
  20. }
  21.  
  22. void upd(int p, int64_t c, int v = 1, int l = 0, int r = maxn) {
  23. 	push(v, l, r);
  24. 	ad[v] += c;
  25. 	if(r - l > 1) {
  26. 		int m = (l + r) / 2;
  27. 		if(p < m) {
  28. 			upd(p, c, 2 * v, l, m);
  29. 		} else {
  30. 			upd(p, c, 2 * v + 1, m, r);
  31. 		}
  32. 	}
  33. }
  34.  
  35. void add(int a, int b, int c, int v = 1, int l = 0, int r = maxn) {
  36. 	push(v, l, r);
  37. 	if(a <= l && r <= b) {
  38. 		px[v] += c;
  39. 		push(v, l, r);
  40. 	} else if(r <= a || b <= l) {
  41. 		return;
  42. 	} else {
  43. 		int m = (l + r) / 2;
  44. 		add(a, b, c, 2 * v, l, m);
  45. 		add(a, b, c, 2 * v + 1, m, r);
  46. 		sm[v] = sm[2 * v] + sm[2 * v + 1];
  47. 	}
  48. }
  49.  
  50. int n;
  51. vector<int> g[maxn];
  52. vector<int> V;
  53. int in[maxn], out[maxn], sz[maxn];
  54. int t;
  55.  
  56. void dfs_sum(int v = 0, int p = 0, int h = 0) {
  57. 	in[v] = t++;
  58. 	sz[v] = 1;
  59. 	for(auto u: g[v]) {
  60. 		if(u != p) {
  61. 			dfs_sum(u, v, h + 1);
  62. 			add(in[u], out[u], 1);
  63. 			sz[v] += sz[u];
  64. 		}
  65. 	}
  66. 	upd(in[v], 1LL * V[v] * sz[v]);
  67. 	out[v] = t;
  68. }
  69.  
  70. int64_t dfs(int v = 0, int p = 0) {
  71. 	int64_t res = sm[1];
  72. 	auto A = sm[1];
  73. 	upd(in[v], 1LL * V[v] * (n - 2 * sz[v] + 1));
  74. 	for(auto u: g[v]) {
  75. 		if(u != p) {
  76. 			add(in[u], out[u], -1);
  77. 			add(0, in[u], 1);
  78. 			add(out[u], n, 1);
  79. 			res = min(res, dfs(u, v));
  80. 			add(in[u], out[u], 1);
  81. 			add(0, in[u], -1);
  82. 			add(out[u], n, -1);
  83. 		}
  84. 	}
  85. 	upd(in[v], 1LL * V[v] * (2 * sz[v] - n - 1));
  86. 	assert(A == sm[1]);
  87. 	return res;
  88. }
  89.  
  90. class RootItRight {
  91. public:
  92. 	long long findMinimumTotalCost(int N, vector <int> edge, vector <int> val, int D, int seed, int MX) {
  93. 		n = N;
  94. 		vector<int> A(2 * N);
  95. 		A[0] = seed;
  96. 		for(int i = 1; i < 2 * N; i++) {
  97. 			A[i] = (A[i - 1] * 1103515245LL + 12345) % 2147483648LL;
  98. 		}
  99. 		auto E = edge;
  100. 		E.resize(N);
  101. 		for(int i = edge.size(); i < N; i++) {
  102. 			E[i] = (A[i] % min(i, D)) + i - min(i, D);
  103. 		}
  104. 		for(int i = 1; i < N; i++) {
  105. 			int u = i, v = E[i];
  106. 			g[u].push_back(v);
  107. 			g[v].push_back(u);
  108.  
  109. 		}
  110. 		V = val;
  111. 		V.resize(N);
  112. 		for(int i = val.size(); i < N; i++) {
  113. 			V[i] = A[N + i] % MX;
  114. 		}
  115. 		dfs_sum();
  116. 		return dfs();
  117. 	}
  118. } me;
  119.  
  120. void print(vector<int> x) {
  121. 	for(auto it: x) {
  122. 		cout << it << ' ';
  123. 	}
  124. 	cout << endl;
  125. }
  126.  
  127. signed main() {
  128. 	//freopen("input.txt", "r", stdin);
  129. 	ios::sync_with_stdio(0);
  130. 	cin.tie(0);
  131. 	cout << me.findMinimumTotalCost(200000,
  132. 									{-1,0,0,0},
  133. 									{4,7},
  134. 									1,
  135. 									0,
  136. 									1000) << endl;
  137. 	return 0;
  138. }
Success #stdin #stdout 0.55s 65984KB
comments (?)
stdin 
Standard input is empty
stdout 
166346919873852152
https://ideone.com/Vxf2zW
language:
C++14 (gcc 8.3)
created:
5 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!