Submission #199378

#	Time	Username	Problem	Language	Result	Execution time	Memory
199378		gs18115	Fireworks (APIO16_fireworks)	C++14	0 / 100	20 ms	26232 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<pl,vector<pl>,less<pl> >pq1[300010];
priority_queue<pl,vector<pl>,greater<pl> >pq2[300010];
int pct;
int pn[300010];
ll b[300010];
ll ans;
inline void pqe(priority_queue<pl,vector<pl>,less<pl> >&pq,ll t)
{
    pl x(t,1);
    if(pq.top().fi==x.fi)
        x.se+=pq.top().se,pq.pop(),pq.ep(x);
    else
        pq.ep(x);
    return;
}
inline void pqe(priority_queue<pl,vector<pl>,greater<pl> >&pq,ll t)
{
    pl x(t,1);
    if(pq.top().fi==x.fi)
        x.se+=pq.top().se,pq.pop(),pq.ep(x);
    else
        pq.ep(x);
    return;
}
inline void pqe(priority_queue<pl,vector<pl>,less<pl> >&pq,pl x)
{
    if(pq.top().fi==x.fi)
        x.se+=pq.top().se,pq.pop(),pq.ep(x);
    else
        pq.ep(x);
    return;
}
inline void pqe(priority_queue<pl,vector<pl>,greater<pl> >&pq,pl x)
{
    if(pq.top().fi==x.fi)
        x.se+=pq.top().se,pq.pop(),pq.ep(x);
    else
        pq.ep(x);
    return;
}
inline void in1(int n,ll x)
{
    if(x>pq2[n].top().fi+b[n])
    {
        ans+=x-(pq2[n].top().fi+b[n]);
        pqe(pq2[n],x-b[n]);
        pl t=pq2[n].top();
        pqe(pq1[n],pq2[n].top().fi);
        pq2[n].pop();
        t.se--;
        if(t.se>0)
            pq2[n].ep(t);
    }
    else
        pqe(pq1[n],x-b[n]);
    return;
}
inline void in2(int n,ll x)
{
    if(x<pq1[n].top().fi+b[n])
    {
        ans+=(pq2[n].top().fi+b[n])-x;
        pqe(pq1[n],x-b[n]);
        pl t=pq1[n].top();
        pqe(pq2[n],pq1[n].top().fi);
        pq1[n].pop();
        t.se--;
        if(t.se>0)
            pq1[n].ep(t);
    }
    else
        pqe(pq2[n],x-b[n]);
    return;
}
inline void in1(int n,pl t)
{
    ll x=t.fi;
    if(x>pq2[n].top().fi+b[n])
    {
        ans+=(x-(pq2[n].top().fi+b[n]))*t.se;
        pqe(pq2[n],pl(x-b[n],t.se));
        pl tt=pq2[n].top();
        pqe(pq1[n],tt.fi);
        pq2[n].pop();
        tt.se--;
        if(tt.se>0)
            pq2[n].ep(tt);
    }
    else
        pqe(pq1[n],pl(x-b[n],t.se));
    return;
}
inline void in2(int n,pl t)
{
    ll x=t.fi;
    if(x<pq1[n].top().fi+b[n])
    {
        ans+=((pq2[n].top().fi+b[n])-x)*t.se;
        pqe(pq1[n],pl(x-b[n],t.se));
        pl tt=pq1[n].top();
        pqe(pq2[n],tt.fi);
        pq1[n].pop();
        tt.se--;
        if(tt.se>0)
            pq1[n].ep(tt);
    }
    else
        pqe(pq2[n],pl(x-b[n],t.se));
    return;
}
void dfs(int x)
{
    if(adj[x].empty())
    {
        pn[x]=pct++;
        pq1[pn[x]].ep(0,1);
        pq2[pn[x]].ep(0,1);
        return;
    }
    int sz=-1;
    for(pl&t:adj[x])
    {
        dfs(t.fi);
        b[pn[t.fi]]+=t.se;
        ll l=pq1[pn[t.fi]].top().fi;
        ll ct=0;
        while(!pq1[pn[t.fi]].empty()&&pq1[pn[t.fi]].top().fi>=l-t.se)
            ct+=pq1[pn[t.fi]].top().se,pq1[pn[t.fi]].pop();
        if(ct>1)
            pq1[pn[t.fi]].ep(l-t.se,ct-1);
        pq1[pn[t.fi]].ep(l,1);
        l=pq2[pn[t.fi]].top().fi;
        while(!pq2[pn[t.fi]].empty())
            pq2[pn[t.fi]].pop();
        pq2[pn[t.fi]].ep(l,1);
        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())
        {
            pl tt=pq1[pn[t.fi]].top();
            tt.fi+=b[pn[t.fi]];
            in1(pn[x],tt);
            pq1[pn[t.fi]].pop();
        }
        while(!pq2[pn[t.fi]].empty())
        {
            pl tt=pq2[pn[t.fi]].top();
            tt.fi+=b[pn[t.fi]];
            in2(pn[x],tt);
            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: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45