Submission #967503

#	Time	Username	Problem	Language	Result	Execution time	Memory
967503		boyliguanhan	Fireworks (APIO16_fireworks)	C++17	100 / 100	401 ms	30204 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);
        } else
            rt[i]=merge(++CC,++CC);
        v[rt[i]]+=C[i];
        v[ch[rt[i]][v[ch[rt[i]][1]]>v[ch[rt[i]][0]]||!ch[rt[i]][0]]]+=C[i];
        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;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:29:30: warning: operation on 'CC' may be undefined [-Wsequence-point]
   29 |             rt[i]=merge(++CC,++CC);
      |                              ^~~~
fireworks.cpp:29:30: warning: operation on 'CC' may be undefined [-Wsequence-point]
fireworks.cpp:24:13: warning: unused variable 'l' [-Wunused-variable]
   24 |         int l=0,r=0;
      |             ^
fireworks.cpp:24:17: warning: unused variable 'r' [-Wunused-variable]
   24 |         int l=0,r=0;
      |                 ^

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