Submission #51698

#	Time	Username	Problem	Language	Result	Execution time	Memory
51698		tmwilliamlin168	Fireworks (APIO16_fireworks)	C++14	100 / 100	381 ms	50168 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=3e5;
int n, m, pi, si[mxN];
vector<int> adj[mxN];
ll c[mxN], yi0[mxN], yi1[mxN];
priority_queue<ll> pc[mxN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=1; i<n+m; ++i) {
		cin >> pi >> c[i], --pi;
		adj[pi].push_back(i);
	}
	for(int i=n+m-1; i>=0; --i) {
		if(i>=n) {
			yi1[i]=-1;
			pc[i].push(0);
			pc[i].push(0);
			si[i]=i;
		} else {
			int mj=adj[i][0];
			for(int j : adj[i])
				if(pc[si[j]].size()<pc[si[j]].size())
					mj=j;
			si[i]=si[mj];
			for(int j : adj[i]) {
				yi0[i]+=yi0[j];
				yi1[i]+=yi1[j];
				if(j==mj)
					continue;
				while(!pc[si[j]].empty()) {
					pc[si[i]].push(pc[si[j]].top());
					pc[si[j]].pop();
				}
			}
		}
		while(pc[si[i]].size()>-yi1[i]+1)
			pc[si[i]].pop();
		ll a1=pc[si[i]].top();
		pc[si[i]].pop();
		ll a2=pc[si[i]].top();
		pc[si[i]].pop();
		pc[si[i]].push(a1+c[i]);
		pc[si[i]].push(a2+c[i]);
		yi0[i]+=c[i];
//		cout << yi0[i] << " " << yi1[i] << endl;
	}
	ll ans=yi0[0];
	pc[si[0]].pop();
	pc[si[0]].push(0);
	while(pc[si[0]].size()>1) {
		ans+=(yi1[0]+pc[si[0]].size()-2)*pc[si[0]].top();
		pc[si[0]].pop();
		ans-=(yi1[0]+pc[si[0]].size()-1)*pc[si[0]].top();
	}
	cout << ans;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:44:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pc[si[i]].size()>-yi1[i]+1)
         ~~~~~~~~~~~~~~~~^~~~~~~~~~

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