Submission #406746

#	Time	Username	Problem	Language	Result	Execution time	Memory
406746		SeDunion	Fireworks (APIO16_fireworks)	C++17	7 / 100	16 ms	23808 KiB

fireworks

#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

ll ans;

vector<pair<int,int>>g[N];

priority_queue<ll>ql;
priority_queue<ll, vector<ll>, greater<ll>>qr;

pair<ll,ll> dfs(int v) {
	if (g[v].empty()) return {0, 0};
	vector<pair<ll,ll>>now;
	for (auto [to, c] : g[v]) {
		auto [nl, nr] = dfs(to);
		now.emplace_back(nl + c, nr + c);
	}
	while(ql.size())ql.pop();
	while(qr.size())qr.pop();
	for (auto [l, r] : now) {
		if (ql.empty() || qr.empty()) {
			assert(ql.empty() && qr.empty());
			ql.push(l);
			qr.push(r);
			continue;
		}
		ll L = ql.top(), R = qr.top();
		if (r <= L) {
			ql.push(l);
			ql.push(r);
			ans += ql.top() - r;
			qr.push(ql.top());
			ql.pop();
		} else if (l >= R) {
			qr.push(l);
			qr.push(r);
			ans += l - qr.top();
			ql.push(qr.top());
			qr.pop();
		} else {
			ql.push(l);
			qr.push(r);
		}
	}
	ll L = ql.top(), R = qr.top();
	return {L, R};
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.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);
	cout << ans;
}

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