Submission #945503

#	Time	Username	Problem	Language	Result	Execution time	Memory
945503		12345678	Fireworks (APIO16_fireworks)	C++17	7 / 100	8 ms	27332 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];
        if (pql[v].size()>pql[u].size()) swap(pql[u], pql[v]), swap(pqr[u], pqr[v]), swap(lz[u], lz[v]);
        //cout<<"here "<<u<<' '<<v<<' '<<pql[u].size()<<' '<<pql[v].size()<<'\n';
        map<ll, ll> mp;
        while (!pql[v].empty()) mp[pql[v].top()+lz[v]]++, pql[v].pop();
        while (!pqr[v].empty()) mp[pqr[v].top()+lz[v]]++, pqr[v].pop();
        for (auto [x, y]:mp)
        {
            for (int i=0; i<y; i+=2)
            {
                //cout<<"add "<<u<<' '<<lz[u]<<' '<<x<<' '<<y<<' '<<i<<'\n';
                ll cur=x;
                if (pql[u].top()+lz[u]<=cur&&cur<=pqr[u].top()+lz[u]) res[u]+=0;
                else res[u]+=min(abs(cur-(pql[u].top()+lz[u])), abs(cur-(pqr[u].top()+lz[u])));
                if (cur-lz[u]>=pqr[u].top()) pqr[u].push(cur-lz[u]), pqr[u].push(cur-lz[u]);
                else pql[u].push(cur-lz[u]), pql[u].push(cur-lz[u]);
                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<<"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