oj.uz

Submission #23501

# Submission time Handle Problem Language Result Execution time Memory
23501 2017-05-11T13:09:07 Z natsukagami Fireworks (APIO16_fireworks) C++14
26 / 100
 0 ms 4132 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4132 KB Output is correct
2 Correct 0 ms 4132 KB Output is correct
3 Correct 0 ms 4132 KB Output is correct
4 Correct 0 ms 4132 KB Output is correct
5 Correct 0 ms 4132 KB Output is correct
6 Correct 0 ms 4132 KB Output is correct
7 Correct 0 ms 4132 KB Output is correct
8 Correct 0 ms 4132 KB Output is correct
9 Correct 0 ms 4132 KB Output is correct
10 Correct 0 ms 4132 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4132 KB Output is correct
2 Correct 0 ms 4132 KB Output is correct
3 Correct 0 ms 4132 KB Output is correct
4 Correct 0 ms 4132 KB Output is correct
5 Correct 0 ms 4132 KB Output is correct
6 Correct 0 ms 4132 KB Output is correct
7 Correct 0 ms 4132 KB Output is correct
8 Correct 0 ms 4132 KB Output is correct
9 Correct 0 ms 4132 KB Output is correct
10 Correct 0 ms 4132 KB Output is correct
11 Correct 0 ms 4132 KB Output is correct
12 Correct 0 ms 4132 KB Output is correct
13 Correct 0 ms 4132 KB Output is correct
14 Correct 0 ms 4132 KB Output is correct
15 Correct 0 ms 4132 KB Output is correct
16 Correct 0 ms 4132 KB Output is correct
17 Correct 0 ms 4132 KB Output is correct
18 Correct 0 ms 4132 KB Output is correct
19 Correct 0 ms 4132 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4132 KB Output is correct
2 Correct 0 ms 4132 KB Output is correct
3 Correct 0 ms 4132 KB Output is correct
4 Correct 0 ms 4132 KB Output is correct
5 Correct 0 ms 4132 KB Output is correct
6 Correct 0 ms 4132 KB Output is correct
7 Correct 0 ms 4132 KB Output is correct
8 Correct 0 ms 4132 KB Output is correct
9 Correct 0 ms 4132 KB Output is correct
10 Correct 0 ms 4132 KB Output is correct
11 Correct 0 ms 4132 KB Output is correct
12 Correct 0 ms 4132 KB Output is correct
13 Correct 0 ms 4132 KB Output is correct
14 Correct 0 ms 4132 KB Output is correct
15 Correct 0 ms 4132 KB Output is correct
16 Correct 0 ms 4132 KB Output is correct
17 Correct 0 ms 4132 KB Output is correct
18 Correct 0 ms 4132 KB Output is correct
19 Correct 0 ms 4132 KB Output is correct
20 Correct 0 ms 4132 KB Output is correct
21 Correct 0 ms 4132 KB Output is correct
22 Correct 0 ms 4132 KB Output is correct
23 Correct 0 ms 4132 KB Output is correct
24 Correct 0 ms 4132 KB Output is correct
25 Correct 0 ms 4132 KB Output is correct
26 Correct 0 ms 4132 KB Output is correct
27 Correct 0 ms 4132 KB Output is correct
28 Correct 0 ms 4132 KB Output is correct
29 Correct 0 ms 4132 KB Output is correct
30 Incorrect 0 ms 4132 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4132 KB Output is correct
2 Correct 0 ms 4132 KB Output is correct
3 Correct 0 ms 4132 KB Output is correct
4 Correct 0 ms 4132 KB Output is correct
5 Correct 0 ms 4132 KB Output is correct
6 Correct 0 ms 4132 KB Output is correct
7 Correct 0 ms 4132 KB Output is correct
8 Correct 0 ms 4132 KB Output is correct
9 Correct 0 ms 4132 KB Output is correct
10 Correct 0 ms 4132 KB Output is correct
11 Correct 0 ms 4132 KB Output is correct
12 Correct 0 ms 4132 KB Output is correct
13 Correct 0 ms 4132 KB Output is correct
14 Correct 0 ms 4132 KB Output is correct
15 Correct 0 ms 4132 KB Output is correct
16 Correct 0 ms 4132 KB Output is correct
17 Correct 0 ms 4132 KB Output is correct
18 Correct 0 ms 4132 KB Output is correct
19 Correct 0 ms 4132 KB Output is correct
20 Correct 0 ms 4132 KB Output is correct
21 Correct 0 ms 4132 KB Output is correct
22 Correct 0 ms 4132 KB Output is correct
23 Correct 0 ms 4132 KB Output is correct
24 Correct 0 ms 4132 KB Output is correct
25 Correct 0 ms 4132 KB Output is correct
26 Correct 0 ms 4132 KB Output is correct
27 Correct 0 ms 4132 KB Output is correct
28 Correct 0 ms 4132 KB Output is correct
29 Correct 0 ms 4132 KB Output is correct
30 Incorrect 0 ms 4132 KB Output isn't correct
31 Halted 0 ms 0 KB -