Submission #479926

#	Time	Username	Problem	Language	Result	Execution time	Memory
479926		sam571128	Fireworks (APIO16_fireworks)	C++17	100 / 100	355 ms	75000 KiB

fireworks

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 6e5+5;
vector<pair<int,int>> adj[N];

int dp[N], to[N], deg[N], ans = 0;

__gnu_pbds::priority_queue<int> pq[N];

void dfs(int u, int p){
    for(auto [v,w] : adj[u]){
        if(v == p) continue;
        dfs(v,u);
        pq[u].join(pq[v]);
    }

    if(u==1) return;

    int l = 0, r = 0;

    if(deg[u]){
        while(--deg[u]){
            pq[u].pop();
        }

        r = pq[u].top();
        pq[u].pop();

        l = pq[u].top();
        pq[u].pop();
    }

    pq[u].push(l+to[u]);
    pq[u].push(r+to[u]);
}

signed main(){
    fastio
    int n,m;
    cin >> n >> m;
    for(int i = 2;i <= n;i++){
        int p,x;
        cin >> p >> x;
        to[i] = x;
        adj[p].push_back({i,x});
        adj[i].push_back({p,x});
        deg[p]++;
        ans += x;
    }
    for(int i = 1;i <= m;i++){
        int p,x;
        cin >> p >> x;
        to[n+i] = x;
        adj[p].push_back({i+n,x});
        adj[i+n].push_back({p,x});
        deg[p]++;
        ans += x;
    }

    dfs(1,-1);

    while(deg[1]--){
        pq[1].pop();
    }

    while(!pq[1].empty()){
        ans -= pq[1].top();
        pq[1].pop();
    }


    cout << ans << "\n";
}

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