fork download
copy 
  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. 	for(auto u: g[v]) {
  73. 		if(u != p) {
  74. 			upd(in[v], 1LL * V[v] * (n - sz[v] - sz[u]));
  75. 			add(in[u], out[u], -1);
  76. 			add(0, in[u], 1);
  77. 			add(out[u], n, 1);
  78. 			res = min(res, dfs(u, v));
  79. 			add(in[u], out[u], 1);
  80. 			add(0, in[u], -1);
  81. 			add(out[u], n, -1);
  82. 			upd(in[v], 1LL * V[v] * (sz[v] + sz[u] - n));
  83. 		}
  84. 	}
  85. 	return res;
  86. }
  87.  
  88. class RootItRight {
  89. public:
  90. 	long long findMinimumTotalCost(int N, vector <int> edge, vector <int> val, int D, int seed, int MX) {
  91. 		n = N;
  92. 		vector<int> A(2 * N);
  93. 		A[0] = seed;
  94. 		for(int i = 1; i < 2 * N; i++) {
  95. 			A[i] = (A[i - 1] * 1103515245LL + 12345) % 2147483648LL;
  96. 		}
  97. 		auto E = edge;
  98. 		E.resize(N);
  99. 		for(int i = edge.size(); i < N; i++) {
  100. 			E[i] = (A[i] % min(i, D)) + i - min(i, D);
  101. 		}
  102. 		for(int i = 1; i < N; i++) {
  103. 			int u = i, v = E[i];
  104. 			g[u].push_back(v);
  105. 			g[v].push_back(u);
  106.  
  107. 		}
  108. 		V = val;
  109. 		V.resize(N);
  110. 		for(int i = val.size(); i < N; i++) {
  111. 			V[i] = A[N + i] % MX;
  112. 		}
  113. 		dfs_sum();
  114. 		return dfs();
  115. 	}
  116. } me;
  117.  
  118. void print(vector<int> x) {
  119. 	for(auto it: x) {
  120. 		cout << it << ' ';
  121. 	}
  122. 	cout << endl;
  123. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/x86_64-linux-gnu/6/../../../x86_64-linux-gnu/Scrt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/9fgmC2
language:
C++14 (gcc 8.3)
created:
4 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!