Submission #51699

#	Time	Username	Problem	Language	Result	Execution time	Memory
51699		tmwilliamlin168	Fireworks (APIO16_fireworks)	C++14	100 / 100	275 ms	48968 KiB

fireworks

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

#define ll long long

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(ll x) {
	ll rev=x;
	int c=0;
	if(!x) {
		putchar_unlocked('0');
		return;
	}
	while(!(rev%10)) {
		++c;
		rev/=10;
	}
	rev=0;
	while(x) {
		rev=rev*10+x%10;
		x/=10;
	}
	while(rev) {
		putchar_unlocked(rev%10+'0');
		rev/=10;
	}
	while(c--)
		putchar_unlocked('0');
}

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

int main() {
	n=in(), m=in();
	for(int i=1; i<n+m; ++i) {
		adj[in()-1].push_back(i);
		c[i]=in();
	}
	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];
	}
	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();
	}
	out(ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:82: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