Submission #115492

#	Time	Username	Problem	Language	Result	Execution time	Memory
115492		KCSC	Fireworks (APIO16_fireworks)	C++14	100 / 100	364 ms	51180 KiB

fireworks

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

const int DIM = 300005;

struct Dp {
	long long a, b;
	priority_queue<long long> *points;
};

Dp dp[DIM];
int parent[DIM], length[DIM];

Dp merge(Dp str1, Dp str2) {
	Dp ans;
	ans.a = str1.a + str2.a;
	ans.b = str1.b + str2.b;

	if (str1.points -> size() > str2.points -> size()) {
		ans.points = str1.points;

		while (str2.points -> size()) {
			ans.points -> push(str2.points -> top());
			str2.points -> pop();
		} 
	} else {
		ans.points = str2.points;
		
		while (str1.points -> size()) {
			ans.points -> push(str1.points -> top());
			str1.points -> pop();
		}
	}
	
	return ans;
}


int main(void) {
//	freopen("fireworks.in", "r", stdin);
//	freopen("fireworks.out", "w", stdout);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n + m; ++i) {
		if (i > 1) 
			cin >> parent[i] >> length[i]; 
		dp[i].points = new priority_queue<long long>();
	}	

	for (int i = n + m; i > 1; --i) {
		if (i > n) {
			dp[i].a = 1; dp[i].b = -length[i];
			dp[i].points -> push(length[i]);
			dp[i].points -> push(length[i]);
		} else {
			while (dp[i].a > 1) {
				long long x = dp[i].points -> top();
				dp[i].a--; dp[i].b += x;
				dp[i].points -> pop();
			}

			long long x = dp[i].points -> top(); 
			dp[i].points -> pop();
			long long y = dp[i].points -> top();
			dp[i].points -> pop();

			dp[i].points -> push(x + length[i]);
			dp[i].points -> push(y + length[i]);
			dp[i].b -= length[i];
		}

		dp[parent[i]] = merge(dp[parent[i]], dp[i]);
	}	

	while (dp[1].a > 0) {
		long long x = dp[1].points -> top();
		dp[1].a--; dp[1].b += x;
		dp[1].points -> pop();
	}

	cout << dp[1].b << endl;
	return 0;
}

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