Submission #51697

#	Time	Username	Problem	Language	Result	Execution time	Memory
51697		tmwilliamlin168	Fireworks (APIO16_fireworks)	C++14	100 / 100	761 ms	184876 KiB

fireworks

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

#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second

const int mxN=3e5;
int n, m, pi, ui, si[mxN];
vector<int> adj[mxN];
ll c[mxN], yi0[mxN], yi1[mxN];
set<pli> 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].insert({0, ui++});
			pc[i].insert({0, ui++});
			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)
					pc[si[i]].insert(pc[si[j]].begin(), pc[si[j]].end());
			}
		}
		auto it=pc[si[i]].end();
		while(pc[si[i]].size()>-yi1[i]+1)
			it=pc[si[i]].erase(--it);
		pli p1=*--it;
		it=pc[si[i]].erase(it);
		pli p2=*--it;
		it=pc[si[i]].erase(it);
		it=pc[si[i]].insert(it, {p2.fi+c[i], p2.se});
		it=pc[si[i]].insert(it, {p1.fi+c[i], p1.se});
		yi0[i]+=c[i];
//		cout << yi0[i] << " " << yi1[i] << endl;
	}
	ll ans=yi0[0];
	auto it=pc[si[0]].insert({0, ui++}).fi;
	for(int i=0; i<-yi1[0]; ++i) {
		ans-=(yi1[0]+i)*it->fi;
		ans+=(yi1[0]+i)*(++it)->fi;
	}
	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