Submission #958234

#	Time	Username	Problem	Language	Result	Execution time	Memory
958234		IBory	Fireworks (APIO16_fireworks)	C++17	0 / 100	5 ms	23132 KiB

fireworks

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

const int MAX = 300003;
ll Z[MAX], W[MAX], off[MAX], ans[MAX];
priority_queue<ll> PQ[MAX];
vector<int> G[MAX];

ll DFS(int cur) {
	ll& ret = Z[cur] = 1;
	for (int next : G[cur]) {
		ret += DFS(next);
		if (PQ[cur].size() < PQ[next].size()) {
			swap(PQ[cur], PQ[next]);
			swap(ans[cur], ans[next]);
			swap(off[cur], off[next]);
		}

		if (!PQ[next].empty()) {
			ll a = PQ[cur].top() + off[cur]; PQ[cur].pop();
			ll b = PQ[cur].top() + off[cur]; PQ[cur].push(a - off[cur]);
			ll c = PQ[next].top() + off[next]; PQ[next].pop();
			ll d = PQ[next].top() + off[next]; PQ[next].push(c - off[next]);
			if (c < b) ans[cur] += b - c;
			else if (a < d) ans[cur] += d - a;
		}

		ans[cur] += ans[next];
		while (!PQ[next].empty()) {
			ll n = PQ[next].top(); PQ[next].pop();
			PQ[cur].push(n + off[next] - off[cur]);
		}
	}

	ll t = 0LL;
	if (!PQ[cur].empty()) {
		ll p = PQ[cur].top(); PQ[cur].pop();
		t = p - PQ[cur].top();
	}
	off[cur] += W[cur];
	ll m = (PQ[cur].empty() ? 0LL : PQ[cur].top());
	PQ[cur].push(m - W[cur]);
	PQ[cur].push(m + t);
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	N += M;
	for (int i = 2; i <= N; ++i) {
		int a, b;
		cin >> a >> b;
		W[i] = b;
		G[a].push_back(i);
	}

	DFS(1);
	cout << ans[1];
	return 0;
}

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