Submission #329403

#	Time	Username	Problem	Language	Result	Execution time	Memory
329403		tnk2908	Fireworks (APIO16_fireworks)	C++14	100 / 100	213 ms	53368 KiB

fireworks

//
//  main.cpp
//  fireworks
//
//  Created by Trần Nam Khánh on 11/21/20.
//

#include <iostream>
#include <queue>
using namespace std;
const long long nax=3e5+1;
struct data
{
    long long a,b,p,c;
    priority_queue<long long>*q;
    data operator +(data tmp)
    {
        data s;
        s.p=p;
        s.c=c;
        s.a=a+tmp.a;
        s.b=b+tmp.b;
        if(q->size()<tmp.q->size())swap(q,tmp.q);
        s.q=q;
        while(!tmp.q->empty())
        {
            s.q->push(tmp.q->top());
            tmp.q->pop();
        }
        return s;
    }
}d[nax];
long long n,m;
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(long long i=2;i<=n+m;i++)
    {
        cin>>d[i].p>>d[i].c;
    }
    for(long long i=1;i<=n+m;i++)
    {
        d[i].a=0;
        d[i].b=0;
        d[i].q=new priority_queue<long long>;
    }
    for(long long i=n+m;i>n;i--)
    {
        d[i].a=1;
        d[i].b=0;
        d[i].q->push(0);
        d[i].q->push(0);
    }
    for(long long i=n+m;i>=2;i--)
    {
        long long p=d[i].p;
        while(d[i].a>1)
        {
            d[i].a--;
            d[i].b+=d[i].q->top();
            d[i].q->pop();
        }
        d[i].b-=d[i].c;
        long long t1=d[i].q->top();d[i].q->pop();
        long long t0=d[i].q->top();d[i].q->pop();
        d[i].q->push(t0+d[i].c);
        d[i].q->push(t1+d[i].c);
        d[p]=d[p]+d[i];
    }
    while(d[1].a>0)
    {
        d[1].a--;
        d[1].b+=d[1].q->top();
        d[1].q->pop();
    }
    cout<<d[1].b<<endl;
    return 0;
}
/*
 4 6
 1 5
 2 5
 2 8
 3 3
 3 2
 3 3
 2 9
 4 4
 4 3
 */

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