Submission #945504

#	Time	Username	Problem	Language	Result	Execution time	Memory
945504		12345678	Fireworks (APIO16_fireworks)	C++17	7 / 100	8 ms	27480 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;

ll n, m, p, c, lz[nx], res[nx];
vector<pair<ll, ll>> d[nx];
priority_queue<ll> pql[nx];
priority_queue<ll, vector<ll>, greater<ll>> pqr[nx];

void dfs(int u)
{
    if (u>n) return pql[u].push(0), pqr[u].push(0), void();
    for (auto [v, w]:d[u]) 
    {
        dfs(v);
        lz[v]+=w;
        res[u]+=res[v];
        ll upd[2]={pql[v].top()+lz[v], pqr[v].top()+lz[v]};
        if (pql[u].empty()) 
        {
            pql[u].push(upd[0]);
            pqr[u].push(upd[1]);
            continue;
        }
        ll cl=pql[u].top(), cr=pqr[u].top();
        if (cr<upd[0]) res[u]+=(upd[0]-cr);
        else if (upd[1]<cl) res[u]+=cl-upd[1];
        if (upd[0]>=pqr[u].top()) pqr[u].push(upd[0]);
        else pql[u].push(upd[0]);
        if (upd[1]>=pqr[u].top()) pqr[u].push(upd[1]);
        else pql[u].push(upd[1]);
        while (pql[u].size()>pqr[u].size()) pqr[u].push(pql[u].top()), pql[u].pop();
        while (pqr[u].size()>pql[u].size()) pql[u].push(pqr[u].top()), pqr[u].pop();
        //cout<<"size "<<pql[u].size()<<' '<<pqr[u].size()<<'\n';
    }
    //cout<<res[u]<<'\n';
    /*
    cout<<"debug : "<<u<<'\n';
    cout<<"l : ";
    priority_queue<ll> l=pql[u];
    priority_queue<ll, vector<ll>, greater<ll>> r=pqr[u];
    while (!l.empty()) cout<<l.top()+lz[u]<<' ', l.pop();
    cout<<'\n';
    cout<<"r : ";
    while (!r.empty()) cout<<r.top()+lz[u]<<' ', r.pop();
    cout<<'\n';
    cout<<"res "<<u<<' '<<res[u]<<'\n';*/
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=2; i<=n+m; i++) cin>>p>>c, d[p].push_back({i, c});
    dfs(1);
    cout<<res[1];
}

/*

*/

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