#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;
template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
int main() {
int n, m; scanf("%d%d", &n, &m);
std::vector<int> leaf(m);
std::vector<std::vector<std::pair<int, i64>>> g(n + m); n += m;
for(int i = 1; i < n; i++) {
int a; i64 b; scanf("%d%lld", &a, &b);
// g[i].push_back({a - 1, b});
g[a - 1].push_back({i, b});
}
std::vector<i64> dist(n, 0);
std::function<void (int, int, i64)> dfs = [&](int v, int par, i64 ari) {
dist[v] = ari;
for(auto e: g[v]) {
if(e.first == par) continue;
dfs(e.first, v, ari + e.second);
}
};
dfs(0, -1, 0);
std::function<i64 (std::vector<i64>&)> OSNIKTR = [](std::vector<i64>& vec) {
i64 X = 0, Y = 1LL << 60;
std::vector<i64> s(vec.size() + 1, 0);
for(int i = 0; i < vec.size(); i++) s[i + 1] = s[i] + vec[i];
for(i64 i = 0; i < vec.size(); i++) {
i64 tmp = std::abs(vec[i]);
tmp += i * vec[i] - s[i];
tmp += (s.back() - s[i]) - ((i64)vec.size() - i) * vec[i];
if(tmp < Y) {
Y = tmp;
X = vec[i];
}
}
return X;
};
i64 tmp = 0;
std::function<i64 (int, int, i64)> solve = [&](int v, int par, i64 t) {
if(v > n - m - 1) return t - (i64)dist[v];
std::vector<i64> vec;
for(auto e: g[v]) {
if(e.first == par) continue;
vec.push_back(solve(e.first, v, t));
}
sort(begin(vec), end(vec));
if(v == 0) {
for(auto v: vec) tmp += std::abs(v);
return 0LL;
}
i64 makino = OSNIKTR(vec);
for(auto v: vec) tmp += std::abs(v - makino);
return makino;
};
i64 ans = 1LL << 60;
if(n <= 300) {
for(int i = 0; i < 301; i++) {
tmp = 0;
solve(0, -1, i);
ans = std::min(ans, tmp);
}
} else {
i64 ok = 0, ng = 1e15;
for(int loop = 0; loop < 100; loop++) {
i64 ml = (ok + ok + ng) / 3LL;
i64 mr = (ok + ng + ng) / 3LL;
tmp = 0;
solve(0, -1, ml);
i64 L = tmp; tmp = 0;
solve(0, -1, mr);
i64 R = tmp;
ans = std::min({ans, L, R});
if(L < R) ng = mr;
else ok = ml;
}
for(i64 i = ok - 1000; i < ok + 1000; i++) {
tmp = 0;
solve(0, -1, i);
ans = std::min(ans, tmp);
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
fireworks.cpp: In lambda function:
fireworks.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); i++) s[i + 1] = s[i] + vec[i];
~~^~~~~~~~~~~~
fireworks.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i64 i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:17:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, m; scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; i64 b; scanf("%d%lld", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
