Submission #1209897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209897		k1r1t0	Fireworks (APIO16_fireworks)	C++20	100 / 100	514 ms	73800 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 310000;

int n, m, p[N], c[N];
vector<int> g[N];
multiset<int> st[N];

void dfs(int v) {
	if (g[v].empty()) {
		st[v].insert(c[v]);
		st[v].insert(c[v]);
		return;
	}
	int slope = 0;
	for (int u : g[v]) {
		dfs(u);
		slope++;
		if (st[u].size() > st[v].size())
			st[u].swap(st[v]);
		for (auto x : st[u])
			st[v].insert(x);
		st[u].clear();
	}
	while (slope > 1) {
		st[v].erase(prev(st[v].end()));
		slope--;
	}
	int r = *st[v].rbegin(); st[v].erase(prev(st[v].end()));
	int l = *st[v].rbegin(); st[v].erase(prev(st[v].end()));
	st[v].insert(l + c[v]);
	st[v].insert(r + c[v]);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	n += m;
	for (int i = 2; i <= n; i++) {
		cin >> p[i] >> c[i];
		g[p[i]].push_back(i);
	}
	dfs(1);
	int ans = 0;
	for (int i = 2; i <= n; i++)
		ans += c[i];
	int slope = st[1].size() - 1;
	int pos = 0;
	for (int k : st[1]) {
		ans -= slope * (k - pos);
		slope--;
		pos = k;
	}
	cout << ans;
}

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