Submission #23501

#	Time	Username	Problem	Language	Result	Execution time	Memory
23501		natsukagami	Fireworks (APIO16_fireworks)	C++14	26 / 100	0 ms	4132 KiB

fireworks

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
const int MAXN = 1e5 + 5;

struct node {
	int total;
	ll off;
	priority_queue<ii> q;
	node() { total = off = 0; }
} *V[MAXN];

void merge(node *&a, node *&b) {
	// merge a <- b
	if (a->q.size() < b->q.size()) swap(a, b); // small to large
	a->total += b->total;
	a->off += b->off;
	while (b->q.size()) { a->q.push(b->q.top()); b->q.pop(); }
}

void opt(node *a, int k) {
	// optimize with k
	a->off += k;
	int mx, mn;
	while (a->total > 0) {
		mx = mn = a->q.top().x;
		a->total -= a->q.top().y;
		a->q.pop(); 
	}
	while (a->total == 0) {
		a->total -= a->q.top().y;
		mn = a->q.top().x; a->q.pop(); 
	}
	// cout << "ck " << mn << ' ' << mx << endl;
	while (a->q.size() && a->q.top().x >= mn) {
		a->total -= a->q.top().y;
		a->q.pop(); 
	}
	// raise total to -1
	a->q.push(ii(mn, -1 - a->total)); 
	// push 0 in
	a->q.push(ii(mn + k, 1)); 
	// push 1 in
	a->q.push(ii(mx + k, 1));
	// fix total
	a->total = 1;
}

int N, M;
int par[MAXN], edge[MAXN], deg[MAXN];

int main() {
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 2; i <= N + M; ++i) {
		cin >> par[i] >> edge[i]; ++deg[par[i]];
	}
	for (int i = 1; i <= N + M; ++i) V[i] = new node();
	for (int i = N + M; i >= 1; --i) {
		if (!deg[i]) {
			// i is leaf
			V[i]->total = 1; V[i]->off = edge[i];
			V[i]->q.push(ii(edge[i], 2));
		} else {
			opt(V[i], edge[i]);
		}
		// cout << "v = " << i << ":" << endl;
		// cout << V[i]->off << ' ' << V[i]->total << endl << "qq:" << endl;
		// auto qq = V[i]->q;
		// while (qq.size()) {
		// 	cout << qq.top().x << ' ' << qq.top().y << endl;
		// 	qq.pop();
		// }
		if (i > 1) merge(V[par[i]], V[i]);
	}
	vector<ii> P; 
	while (V[1]->q.size()) { 
		P.push_back(V[1]->q.top()); 
		V[1]->total -= V[1]->q.top().y; 
		V[1]->q.pop(); 
	}
	reverse(P.begin(), P.end());
	ll ans = V[1]->off, last = 0, cur = V[1]->off;
	for (auto i: P) {
		// cout << i.x << ' ' << i.y << ' ' << V[1]->total << ' ' << cur << endl;
		cur += (i.x - last) * V[1]->total;
		ans = min(ans, cur);
		V[1]->total += i.y;
		last = i.x;
	}
	cout << ans << endl;
}

Compilation message (stderr)

fireworks.cpp: In function 'void opt(node*, int)':
fireworks.cpp:48:18: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  a->q.push(ii(mx + k, 1));
                  ^
fireworks.cpp:39:21: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while (a->q.size() && a->q.top().x >= mn) {
                     ^

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