Submission #964646

#	Time	Username	Problem	Language	Result	Execution time	Memory
964646		thinknoexit	Fireworks (APIO16_fireworks)	C++17	100 / 100	217 ms	94480 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 300300;
bool leaf[N];
vector<pair<int, ll>> adj[N];
ll ans[N];
priority_queue<ll> l[N];
priority_queue<ll, vector<ll>, greater<ll>> r[N];
void dfs(int v, ll p = 0ll, ll d = 0ll) {
    if (leaf[v]) {
        l[v].push(p);
        r[v].push(p);
        return;
    }
    for (auto& [x, w] : adj[v]) {
        dfs(x, w, d + w);
        ans[v] += ans[x];
        if (l[v].empty()) {
            swap(l[v], l[x]);
            swap(r[v], r[x]);
            continue;
        }
        if (l[x].size() + r[x].size() > l[v].size() + r[v].size()) {
            swap(l[v], l[x]);
            swap(r[v], r[x]);
        }
        while (!l[x].empty()) {
            ll now = l[x].top();
            l[x].pop();
            ll nowr = r[v].top();
            if (now <= nowr) l[v].push(now);
            else {
                ans[v] += now - nowr;
                l[v].push(nowr);
                r[v].pop();
                r[v].push(now);
            }
        }
        while (!r[x].empty()) {
            ll now = r[x].top();
            r[x].pop();
            ll nowl = l[v].top();
            if (nowl <= now) r[v].push(now);
            else {
                ans[v] += nowl - now;
                r[v].push(nowl);
                l[v].pop();
                l[v].push(now);
            }
        }
    }
    ll nl = l[v].top() + p;
    l[v].pop();
    l[v].push(nl);
    ll nr = r[v].top() + p;
    while (!r[v].empty()) r[v].pop();
    r[v].push(nr);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 2;i <= n + m;i++) {
        int p;
        ll c;
        cin >> p >> c;
        adj[p].push_back({ i, c });
    }
    for (int i = n + 1;i <= n + m;i++) leaf[i] = 1;
    dfs(1);
    cout << ans[1] << '\n';
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45