Submission #1177079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177079		IBory	Fireworks (APIO16_fireworks)	C++20	7 / 100	8 ms	16712 KiB

fireworks

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 300007;
vector<pii> G[MAX];
priority_queue<ll> X[MAX];
ll A[MAX], B[MAX];

void DFS(int cur) {
	if (G[cur].empty()) {
		X[cur].push(0); X[cur].push(0);
		A[cur] = -1; B[cur] = 0;
		return;
	}

	for (auto [next, d] : G[cur]) DFS(next);

	for (auto [next, d] : G[cur]) {
		ll a = 0;
		while (-1 < (A[next] + (ll)X[next].size())) {
			a = X[next].top();
			X[next].pop();
		}
		a += d;
		X[next].push(a); X[next].push(a);
		B[next] += d;

		// cout << "Info: " << cur << " to " << next << '\n';
		// cout << A[next] << ' ' << B[next] << '\n';
		// vector<ll> temp;
		// while (!X[next].empty()) {
		// 	temp.push_back(X[next].top()); X[next].pop();
		// }
		// for (ll n : temp) X[next].push(n);
		// reverse(temp.begin(), temp.end());
		// for (ll n : temp) cout << n << ' ';
		// cout << '\n';
		// cout << '\n';

		A[cur] += A[next]; B[cur] += B[next];
		if (X[cur].size() < X[next].size()) swap(X[cur], X[next]);
		while (!X[next].empty()) {
			X[cur].push(X[next].top());
			X[next].pop();
		}
	}

	// cout << "Moderate " << cur << '\n';
	// cout << A[cur] << ' ' << B[cur] << '\n';
	// vector<ll> temp;
	// while (!X[cur].empty()) {
	// 	temp.push_back(X[cur].top()); X[cur].pop();
	// }
	// for (ll n : temp) X[cur].push(n);
	// reverse(temp.begin(), temp.end());
	// for (ll n : temp) cout << n << ' ';
	// cout << '\n';
	// cout << "---------------------\n";
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 2; i <= N + M; ++i) {
		int p, c;
		cin >> p >> c;
		G[p].emplace_back(i, c);
	}

	DFS(1);
	ll ans = B[1], slope = A[1], pv = 0;
	vector<ll> S;
	while (!X[1].empty()) {
		S.push_back(X[1].top()); X[1].pop();
	}
	sort(S.begin(), S.end());
	for (ll x : S) {
		ans += slope * (x - pv);
		if (0 < ++slope) break;
		pv = x;
	}

	cout << ans;
	return 0;
}

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