Submission #1306372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306372		HasanV11010238	Fireworks (APIO16_fireworks)	C++20	100 / 100	358 ms	96552 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<vector<ll>>> v;
vector<priority_queue<ll>> pr;
ll ans = 0, n, fi;
void dfs(int x, ll co){
    if (v[x].size() == 0){
        pr[x].push(co);
        pr[x].push(co);
        ans -= co;
        return;
    }
    int cnt = 0;
    for (auto el : v[x]){
        cnt++;
        dfs(el[0], el[1]);
        if (pr[el[0]].size() > pr[x].size()){
            swap(pr[el[0]], pr[x]);
        }
        while (!pr[el[0]].empty()){
            pr[x].push(pr[el[0]].top());
            pr[el[0]].pop();
        }
    }
    int wh = 0;
    if (x != 1) wh++;
    for (int i = wh; i < cnt; i++){
        ans += pr[x].top();
        pr[x].pop();
    }
    if (x != 1){
        ll fi = pr[x].top();
        pr[x].pop();
        ll se = pr[x].top();
        pr[x].pop();
        pr[x].push(fi + co);
        pr[x].push(se + co);
        ans -= co;
    }
}
int main(){
    ll a, b;
    cin>>fi>>n;
    n += fi;
    v.assign(n + 1, vector<vector<ll>>());
    pr.assign(n + 1, priority_queue<ll>());
    for (int i = 2; i <= n; i++){
        cin>>a>>b;
        v[a].push_back({i, b});
    }
    dfs(1, 0);
    cout<<ans;
}

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