Submission #262724

#	Time	Username	Problem	Language	Result	Execution time	Memory
262724		srvlt	Fireworks (APIO16_fireworks)	C++14	100 / 100	364 ms	78192 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 300003;
int n, m;
vector <array <int, 2>> g[n0];

struct Fn {
	int k = 0;
	ll b = 0;
	priority_queue <ll> slp;
	void merge(Fn & f) {
		while (!f.slp.empty()) {
			slp.push(f.slp.top());
			f.slp.pop();
		}
		k += f.k;
		b += f.b;
	}
	void minimize() {
		while (k > 0) {
			k--;
			b += slp.top();
			slp.pop();
		}
	}
	void add(int w) {
		while (k > 1) {
			k--;
			b += slp.top();
			slp.pop();
		}
		if (k < 0) return;
		ll x0 = slp.top() + w;
		slp.pop();
		if (k == 1) {
			ll x1 = slp.top() + w;
			slp.pop();
			slp.push(x1);
		}
		slp.push(x0);
		b -= w;
	}
};
Fn f[n0];

void swap(Fn & x, Fn & y) {
	swap(x.k, y.k), swap(x.b, y.b), x.slp.swap(y.slp);
}

void merge(int x, int y) {
	if (SZ(f[x].slp) < SZ(f[y].slp)) swap(f[x], f[y]);
	f[x].merge(f[y]);
}

Fn cur;

void dfs(int v, int p) {
	for (auto i : g[v]) {
		int to = i[0], w = i[1];
		if (to == p) continue;
		dfs(to, v);
		if (SZ(g[to]) == 0) {
			while (!cur.slp.empty()) cur.slp.pop();
			cur.slp.push(w), cur.slp.push(w);
			cur.k = 1, cur.b = -w;
			f[v].merge(cur);
		}	else {
			f[to].add(w);
			merge(v, to);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m;
	for (int i = 2; i <= n + m; i++) {
		int x, w;
		cin >> x >> w;
		g[x].pb({i, w});
	}
	dfs(1, 1);
	f[1].minimize();
	cout << f[1].b;
}

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