Submission #199381

#	Time	Username	Problem	Language	Result	Execution time	Memory
199381		gs18115	Fireworks (APIO16_fireworks)	C++14	100 / 100	326 ms	83832 KiB

fireworks

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
vector<pl>adj[300010];
priority_queue<ll,vector<ll>,less<ll> >pq1[300010];
priority_queue<ll,vector<ll>,greater<ll> >pq2[300010];
int pct;
int pn[300010];
ll b1[300010],b2[300010];
ll ans;
inline void in1(int n,ll x)
{
    if(x>pq2[n].top()+b2[n])
    {
        ans+=x-(pq2[n].top()+b2[n]);
        pq2[n].ep(x-b2[n]);
        pq1[n].ep(pq2[n].top()+b2[n]-b1[n]);
        pq2[n].pop();
    }
    else
        pq1[n].ep(x-b1[n]);
    return;
}
inline void in2(int n,ll x)
{
    if(x<pq1[n].top()+b1[n])
    {
        ans+=(pq1[n].top()+b1[n])-x;
        pq1[n].ep(x-b1[n]);
        pq2[n].ep(pq1[n].top()+b1[n]-b2[n]);
        pq1[n].pop();
    }
    else
        pq2[n].ep(x-b2[n]);
    return;
}
void dfs(int x)
{
    if(adj[x].empty())
    {
        pn[x]=pct++;
        pq1[pn[x]].ep(0);
        pq2[pn[x]].ep(0);
        return;
    }
    int sz=-1;
    for(pl&t:adj[x])
    {
        dfs(t.fi);
        b2[pn[t.fi]]+=t.se;
        ll l=pq1[pn[t.fi]].top();
        pq1[pn[t.fi]].pop();
        pq1[pn[t.fi]].ep(l+t.se);
        l=pq2[pn[t.fi]].top();
        while(!pq2[pn[t.fi]].empty())
            pq2[pn[t.fi]].pop();
        pq2[pn[t.fi]].ep(l);
        if(sz<(int)pq1[pn[t.fi]].size())
            sz=pq1[pn[x]=pn[t.fi]].size();
    }
    for(pl&t:adj[x])
    {
        if(pn[x]==pn[t.fi])
            continue;
        while(!pq1[pn[t.fi]].empty())
            in1(pn[x],pq1[pn[t.fi]].top()+b1[pn[t.fi]]),pq1[pn[t.fi]].pop();
        while(!pq2[pn[t.fi]].empty())
            in2(pn[x],pq2[pn[t.fi]].top()+b2[pn[t.fi]]),pq2[pn[t.fi]].pop();
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int v,c,p;
    cin>>v>>c;
    v+=c;
    for(int i=1;i++<v;)
        cin>>p>>c,adj[p].eb(i,c);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

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