Submission #92220

#	Time	Username	Problem	Language	Result	Execution time	Memory
92220		moonrabbit2	Fireworks (APIO16_fireworks)	C++17	100 / 100	191 ms	51088 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll N=3e5+5;
int n,m,p[N],c[N];
struct ddata
{
    ll a,b;
    priority_queue<ll> *pq;
    ddata operator +(ddata k){
        ddata res;
        tie(res.a,res.b)=P(a+k.a,b+k.b);
        if(pq->size()>=k.pq->size()){
            res.pq=pq;
            while(k.pq->size()){
                res.pq->push(k.pq->top());
                k.pq->pop();
            }
        }
        else{
            res.pq=k.pq;
            while(pq->size()){
                res.pq->push(pq->top());
                pq->pop();
            }
        }
        return res;
    }
};
ddata a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n+m;i++) cin>>p[i]>>c[i];
    for(int i=n+m;i>=1;i--){
        a[i].a=a[i].b=0;
        a[i].pq=new priority_queue<ll>;
    }
    for(int i=n+m;i>n;i--){
        a[i].a=1; a[i].b=-c[i];
        a[i].pq->push(c[i]); a[i].pq->push(c[i]);
        a[p[i]]=a[p[i]]+a[i];
    }
    for(int i=n;i>=2;i--){
        while(a[i].a>1){
            a[i].a--;
            a[i].b+=a[i].pq->top();
            a[i].pq->pop();
        }
        ll t1=a[i].pq->top();
        a[i].pq->pop();
        ll t2=a[i].pq->top();
        a[i].pq->pop();
        a[i].pq->push(t1+c[i]); a[i].pq->push(t2+c[i]);
        a[i].b-=c[i];
        a[p[i]]=a[p[i]]+a[i];
    }
    while(a[1].a>0){
        a[1].a--;
        a[1].b+=a[1].pq->top();
        a[1].pq->pop();
    }
    cout<<a[1].b;
    return 0;
}

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