#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>
long long N = 0, M = 0;
// 0 -> parent number, 1 -> edge's weight
long long parent [300005][2];
long long leaf [300005];
std::deque<long long> child [300005];
std::vector<long long> segtree [300005];
long long partial_solver(long long node, long long t, long long offset);
//
long long partial_solver_odd(long long node, long long t, long long offset) {
long long original = parent[node][1];
long long mid = segtree[node][segtree[node].size() / 2] - offset;
long long change = t - mid;
if(change + original < 0) change = -original;
// printf("t: %lld, mid: %lld, node: %lld, change : %lld,\n\n\n", t, mid, node, change);
long long sum = std::abs(change);
for(long long i : child[node])
sum += partial_solver(i, t - (original + change), offset + (original + change));
return sum;
}
long long partial_solver_even(long long node, long long t, long long offset) {
long long original = parent[node][1];
long long mid1 = segtree[node][segtree[node].size() / 2 - 1] - offset;
long long mid2 = segtree[node][segtree[node].size() / 2] - offset;
long long change1 = t - mid2;
long long change2 = t - mid1;
long long change = 0;
if(change2 < 0) {
change = change2;
if(change2 + original < 0)
change = -original;
}
if(change1 <= 0 && change2 >= 0)
change = 0;
if(change1 > 0)
change = change1;
// printf("t: %lld, mid1: %lld, mid2: %lld, node: %lld, change1 : %lld,\nchange2 : %lld, change: %lld\n\n\n", t, mid1, mid2, node, change1, change2, change);
long long sum = std::abs(change);
for(long long i : child[node]) {
sum += partial_solver(i, t - (original + change), offset + (original + change));
}
return sum;
}
long long partial_solver(long long node, long long t, long long offset) {
if(child[node].empty()) {
// printf(" hehe %lld\n", t);
return std::abs(t - parent[node][1]);
}
if(segtree[node].size() % 2)
return partial_solver_odd(node, t, offset);
return partial_solver_even(node, t, offset);
}
long long partial_solver(long long t) {
long long ans = 0;
for(long long i : child[1])
ans += partial_solver(i, t, 0);
return ans;
}
long long solver() {
long long first = 0, last = 1e17, min = 1e17;
while(first + 2 < last) {
long long mid1arg = (2 * first + last) / 3;
long long mid2arg = (first + 2 * last) / 3;
// printf("mid1arg %lld mid2arg %lld\n", mid1arg, mid2arg);
long long mid1 = partial_solver(mid1arg);
long long mid2 = partial_solver(mid2arg);
if(mid1 <= mid2) last = mid2arg;
if(mid1 >= mid2) first = mid1arg;
}
for(long long i = first; i <= last; i++)
if(partial_solver(min) > partial_solver(i))
min = i;
return partial_solver(min);
}
void construct() {
for(long long i = N + 1; i <= N + M; i++) {
auto get_cost = [&]() -> long long {
long long node = i, sum = 0;
while(node) {
sum = parent[node][1] + sum;
node = parent[node][0];
}
return sum;
};
auto append = [&](int cost_root_to_leaf) -> void {
long long node = i;
while(node) {
segtree[node].push_back(cost_root_to_leaf);
node = parent[node][0];
}
};
append(get_cost());
}
for(long long i = 1; i <= N + M; i++)
std::sort(segtree[i].begin(), segtree[i].end());
}
int main() {
scanf("%lld%lld", &N, &M);
for(long long i = 2; i <= N; i++) {
long long i_parent = 0, i_weight = 0;
scanf("%lld%lld", &i_parent, &i_weight);
parent[i][0] = i_parent;
parent[i][1] = i_weight;
child [i_parent] . push_back(i);
}
for(long long i = N + 1; i <= N + M; i++) {
long long i_parent = 0, i_weight = 0;
scanf("%lld%lld", &i_parent, &i_weight);
parent[i][0] = i_parent;
parent[i][1] = i_weight;
child [i_parent] . push_back(i);
}
construct();
printf("%lld", solver());
}
Compilation message
fireworks.cpp: In function 'int main()':
fireworks.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%lld%lld", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | scanf("%lld%lld", &i_parent, &i_weight);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
131 | scanf("%lld%lld", &i_parent, &i_weight);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
209400 KB |
Output is correct |
| 2 |
Correct |
150 ms |
209372 KB |
Output is correct |
| 3 |
Correct |
150 ms |
209272 KB |
Output is correct |
| 4 |
Correct |
171 ms |
209272 KB |
Output is correct |
| 5 |
Correct |
165 ms |
209272 KB |
Output is correct |
| 6 |
Correct |
162 ms |
209400 KB |
Output is correct |
| 7 |
Incorrect |
171 ms |
209272 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
209288 KB |
Output is correct |
| 2 |
Incorrect |
175 ms |
209272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
209400 KB |
Output is correct |
| 2 |
Correct |
150 ms |
209372 KB |
Output is correct |
| 3 |
Correct |
150 ms |
209272 KB |
Output is correct |
| 4 |
Correct |
171 ms |
209272 KB |
Output is correct |
| 5 |
Correct |
165 ms |
209272 KB |
Output is correct |
| 6 |
Correct |
162 ms |
209400 KB |
Output is correct |
| 7 |
Incorrect |
171 ms |
209272 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
209400 KB |
Output is correct |
| 2 |
Correct |
150 ms |
209372 KB |
Output is correct |
| 3 |
Correct |
150 ms |
209272 KB |
Output is correct |
| 4 |
Correct |
171 ms |
209272 KB |
Output is correct |
| 5 |
Correct |
165 ms |
209272 KB |
Output is correct |
| 6 |
Correct |
162 ms |
209400 KB |
Output is correct |
| 7 |
Incorrect |
171 ms |
209272 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
