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. 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
stdin
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
Standard output is empty