Submission #367719

#	Time	Username	Problem	Language	Result	Execution time	Memory
367719		YJU	Fireworks (APIO16_fireworks)	C++14	100 / 100	236 ms	53208 KiB

fireworks

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct data{
	ll a,b;
	priority_queue<ll> *pq;
	data operator+(data B){
		data s;
		s.a=a+B.a;
		s.b=b+B.b;
		if(pq->size()>B.pq->size()){
			s.pq=pq;
			while(!B.pq->empty()){
				s.pq->push(B.pq->top());
				B.pq->pop();
			}
		}else{
			s.pq=B.pq;
			while(!pq->empty()){
				s.pq->push(pq->top());
				pq->pop();
			}
		}
		return s;
	}
}d[N];

ll n,m,p[N],c[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	for(int i=2;i<=n+m;i++){
		cin>>p[i]>>c[i];
	}
	REP1(i,n+m)d[i].a=d[i].b=0,d[i].pq=new priority_queue<ll>;
	for(int i=n+m;i>n;i--){
		d[i].a=1;
		d[i].b=-c[i];
		d[i].pq->push(c[i]);
		d[i].pq->push(c[i]);
		d[p[i]]=d[p[i]]+d[i];
	}
	for(int i=n;i>1;i--){
		while(d[i].a>1){
			--d[i].a;
			d[i].b+=d[i].pq->top();
			d[i].pq->pop();
		}
		ll tmpa=d[i].pq->top();d[i].pq->pop();
		ll tmpb=d[i].pq->top();d[i].pq->pop();
		d[i].pq->push(tmpa+c[i]);
		d[i].pq->push(tmpb+c[i]);
		d[i].b-=c[i];
		d[p[i]]=d[p[i]]+d[i];
	}
	while(d[1].a>0){
		--d[1].a;
		d[1].b+=d[1].pq->top();
		d[1].pq->pop();
	}
	cout<<d[1].b<<"\n";
	return 0;
}

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