Submission #544684

#	Time	Username	Problem	Language	Result	Execution time	Memory
544684		valerikk	Fireworks (APIO16_fireworks)	C++17	100 / 100	217 ms	58608 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 300500;

int n, m;
int p[N];
ll c[N];
vector<int> g[N];
ll base[N];
ll d[N];
priority_queue<ll, vector<ll>> q[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n + m; ++i) {
		cin >> p[i] >> c[i];
		--p[i];
		g[p[i]].push_back(i);
	}
	
	c[0] = 0;
	for (int i = n; i < n + m; ++i) {
		base[i] = c[i];
		d[i] = -1;
		q[i].push(c[i]);
		q[i].push(c[i]);
	}
	
	for (int i = n - 1; i >= 0; --i) {
		int mx = g[i][0];
		for (int j : g[i]) {
			if (q[i].size() > q[mx].size()) {
				mx = j;
			}
			base[i] += base[j];
			d[i] += d[j];
		}
		swap(q[i], q[mx]);
		for (int j : g[i]) {
			if (j != mx) {
				while (!q[j].empty()) {
					q[i].push(q[j].top());
					q[j].pop();
				}
			}
		}

		while (d[i] + q[i].size() > 1) {
			q[i].pop();
		}

		ll x = q[i].top();
		q[i].pop();
		ll y = q[i].top();
		q[i].pop();
		q[i].push(x + c[i]);
		q[i].push(y + c[i]);
		base[i] += c[i];
	}

	vector<ll> a;
	while (!q[0].empty()) {
		a.push_back(q[0].top());
		q[0].pop();
	}
	reverse(a.begin(), a.end());

	ll ans = base[0];
	ll diff = d[0];	
	if (diff < 0) {
		ans += diff * a[0];
	}
	for (int i = 0; i < (int)a.size() - 1; ++i) {
		diff += 1;
		ans += diff * (a[i + 1] - a[i]);
	}
	cout << ans << endl;
	return 0;
}

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