#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct edge {
int to, w;
edge() {}
edge(int tt, int ww) {
to = tt;
w = ww;
}
};
struct func {
multiset<ll> s;
ll st;
func() {
clear();
}
void clear() {
s.clear();
s.insert(0);
s.insert(0);
st = 0;
}
void insert(ll x) {
s.insert(x);
}
void upd(const func &a) {
st += a.st;
for (const auto &i : a.s)
s.insert(i);
s.erase(prev(s.end()));
}
void shift(ll x) {
st += x;
vector<ll> v;
if (s.size()) v.push_back(*prev(s.end())), s.erase(prev(s.end()));
if (s.size()) v.push_back(*prev(s.end())), s.erase(prev(s.end()));
while (v.size()) {
s.insert(s.end(), v.back() + x);
v.pop_back();
}
}
void print() {
cout << "s: ";
for (const auto &i : s) cout << i << " "; cout << '\n';
cout << "start: " << st << '\n';
}
};
int n;
vector<vector<edge>> g;
vector<int> sz;
void dfs(int v, int prev, func &f) {
int big = -1, sh;
for (const auto &i : g[v])
if (i.to != prev && (big == -1 || sz[big] < sz[i.to])) big = i.to, sh = i.w;
if (big == -1) {
f = func();
return;
}
dfs(big, v, f);
f.shift(sh);
func f2;
for (const auto &i : g[v]) {
if (i.to != prev && i.to != big) {
f2.clear();
dfs(i.to, v, f2);
f2.shift(i.w);
f.upd(f2);
}
}
if (OO) {
cout << "finishing node " << v << '\n';
f.print();
cout << '\n';
}
}
int dfs(int v = 0, int prev = 0) {
sz[v] = 1;
for (const auto &i : g[v])
if (i.to != prev)
sz[v] += dfs(i.to, v);
return sz[v];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int useless;
cin >> n >> useless;
n += useless;
g.resize(n);
for (int i = 1, p, w; i < n; i++) {
cin >> p >> w;
--p;
g[p].push_back(edge(i, w));
g[i].push_back(edge(p, w));
}
sz.resize(n);
dfs();
func f;
dfs(0, 0, f);
ll ans = f.st;
ll pos = 0;
ll slope = (ll)f.s.size() - 1;
auto it = f.s.begin();
while (slope > 0) {
ans -= slope * (*it - pos);
pos = *it;
slope--;
it++;
}
finish(ans);
}
Compilation message
fireworks.cpp: In member function 'void func::print()':
fireworks.cpp:54:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : s) cout << i << " "; cout << '\n';
^~~
fireworks.cpp:54:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : s) cout << i << " "; cout << '\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
