Submission #967500

#	Time	Username	Problem	Language	Result	Execution time	Memory
967500		boyliguanhan	Fireworks (APIO16_fireworks)	C++17	100 / 100	397 ms	37972 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#define N 5<<17
#define pop(X) rt[X]=merge(ch[rt[X]][0],ch[rt[X]][1])
#define int long long
int deg[N],P[N],C[N],rt[N],ch[N][2],v[N],CC;
mt19937 rng(9234623);
int merge(int a,int b){
    if(!a+!b)
        return a+b;
    if(v[a]<v[b])
        swap(a,b);
    int x=rng()%2;
    ch[a][x]=merge(ch[a][x],b);
    return a;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=2;i<=n+m;i++)
        cin>>P[i]>>C[i],deg[P[i]]++,ans+=C[i];
    for(int i=n+m;i>1;i--){
        int l=0,r=0;
        if(deg[i]){
            while(--deg[i])
                pop(i);
            r=v[rt[i]];
            pop(i);
            l=v[rt[i]];
            pop(i);
        }
        v[++CC]=l+C[i],v[++CC]=r+C[i];
        rt[i]=merge(rt[i],merge(CC,CC-1));
        rt[P[i]]=merge(rt[P[i]],rt[i]);
    }
    while(deg[1]--)
        pop(1);
    while(rt[1])
        ans-=v[rt[1]],pop(1);
    cout<<ans;
}

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