Submission #544684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544684	2022-04-02T14:22:49 Z	valerikk	Fireworks (APIO16_fireworks)	C++17	100 / 100	217 ms	58608 KB

fireworks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 300500;

int n, m;
int p[N];
ll c[N];
vector<int> g[N];
ll base[N];
ll d[N];
priority_queue<ll, vector<ll>> q[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n + m; ++i) {
		cin >> p[i] >> c[i];
		--p[i];
		g[p[i]].push_back(i);
	}
	
	c[0] = 0;
	for (int i = n; i < n + m; ++i) {
		base[i] = c[i];
		d[i] = -1;
		q[i].push(c[i]);
		q[i].push(c[i]);
	}
	
	for (int i = n - 1; i >= 0; --i) {
		int mx = g[i][0];
		for (int j : g[i]) {
			if (q[i].size() > q[mx].size()) {
				mx = j;
			}
			base[i] += base[j];
			d[i] += d[j];
		}
		swap(q[i], q[mx]);
		for (int j : g[i]) {
			if (j != mx) {
				while (!q[j].empty()) {
					q[i].push(q[j].top());
					q[j].pop();
				}
			}
		}

		while (d[i] + q[i].size() > 1) {
			q[i].pop();
		}

		ll x = q[i].top();
		q[i].pop();
		ll y = q[i].top();
		q[i].pop();
		q[i].push(x + c[i]);
		q[i].push(y + c[i]);
		base[i] += c[i];
	}

	vector<ll> a;
	while (!q[0].empty()) {
		a.push_back(q[0].top());
		q[0].pop();
	}
	reverse(a.begin(), a.end());

	ll ans = base[0];
	ll diff = d[0];	
	if (diff < 0) {
		ans += diff * a[0];
	}
	for (int i = 0; i < (int)a.size() - 1; ++i) {
		diff += 1;
		ans += diff * (a[i + 1] - a[i]);
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	9 ms	16812 KB	Output is correct
3	Correct	9 ms	16808 KB	Output is correct
4	Correct	9 ms	16724 KB	Output is correct
5	Correct	9 ms	16816 KB	Output is correct
6	Correct	9 ms	16724 KB	Output is correct
7	Correct	9 ms	16724 KB	Output is correct
8	Correct	9 ms	16724 KB	Output is correct
9	Correct	10 ms	16812 KB	Output is correct
10	Correct	9 ms	16808 KB	Output is correct
11	Correct	10 ms	16748 KB	Output is correct
12	Correct	11 ms	16760 KB	Output is correct
13	Correct	9 ms	16816 KB	Output is correct
14	Correct	11 ms	16724 KB	Output is correct
15	Correct	9 ms	16772 KB	Output is correct
16	Correct	9 ms	16852 KB	Output is correct
17	Correct	10 ms	16808 KB	Output is correct
18	Correct	10 ms	16852 KB	Output is correct
19	Correct	9 ms	16852 KB	Output is correct

Subtask #3
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	10 ms	16724 KB	Output is correct
3	Correct	10 ms	16724 KB	Output is correct
4	Correct	9 ms	16784 KB	Output is correct
5	Correct	9 ms	16724 KB	Output is correct
6	Correct	9 ms	16724 KB	Output is correct
7	Correct	10 ms	16724 KB	Output is correct
8	Correct	9 ms	16724 KB	Output is correct
9	Correct	9 ms	16812 KB	Output is correct
10	Correct	9 ms	16724 KB	Output is correct
11	Correct	9 ms	16724 KB	Output is correct
12	Correct	9 ms	16812 KB	Output is correct
13	Correct	9 ms	16808 KB	Output is correct
14	Correct	9 ms	16724 KB	Output is correct
15	Correct	9 ms	16816 KB	Output is correct
16	Correct	9 ms	16724 KB	Output is correct
17	Correct	9 ms	16724 KB	Output is correct
18	Correct	9 ms	16724 KB	Output is correct
19	Correct	10 ms	16812 KB	Output is correct
20	Correct	9 ms	16808 KB	Output is correct
21	Correct	10 ms	16748 KB	Output is correct
22	Correct	11 ms	16760 KB	Output is correct
23	Correct	9 ms	16816 KB	Output is correct
24	Correct	11 ms	16724 KB	Output is correct
25	Correct	9 ms	16772 KB	Output is correct
26	Correct	9 ms	16852 KB	Output is correct
27	Correct	10 ms	16808 KB	Output is correct
28	Correct	10 ms	16852 KB	Output is correct
29	Correct	9 ms	16852 KB	Output is correct
30	Correct	9 ms	16748 KB	Output is correct
31	Correct	10 ms	16852 KB	Output is correct
32	Correct	10 ms	16960 KB	Output is correct
33	Correct	12 ms	16980 KB	Output is correct
34	Correct	11 ms	17108 KB	Output is correct
35	Correct	11 ms	17108 KB	Output is correct
36	Correct	11 ms	17108 KB	Output is correct
37	Correct	12 ms	17200 KB	Output is correct
38	Correct	12 ms	17236 KB	Output is correct
39	Correct	11 ms	17236 KB	Output is correct
40	Correct	10 ms	17108 KB	Output is correct
41	Correct	11 ms	17084 KB	Output is correct
42	Correct	12 ms	17180 KB	Output is correct
43	Correct	12 ms	17236 KB	Output is correct
44	Correct	12 ms	17236 KB	Output is correct
45	Correct	12 ms	17236 KB	Output is correct
46	Correct	14 ms	17464 KB	Output is correct
47	Correct	12 ms	17360 KB	Output is correct
48	Correct	11 ms	17236 KB	Output is correct
49	Correct	12 ms	17364 KB	Output is correct
50	Correct	11 ms	17232 KB	Output is correct
51	Correct	12 ms	17208 KB	Output is correct
52	Correct	11 ms	17364 KB	Output is correct
53	Correct	12 ms	17364 KB	Output is correct
54	Correct	12 ms	17364 KB	Output is correct

Subtask #4
45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	10 ms	16724 KB	Output is correct
3	Correct	10 ms	16724 KB	Output is correct
4	Correct	9 ms	16784 KB	Output is correct
5	Correct	9 ms	16724 KB	Output is correct
6	Correct	9 ms	16724 KB	Output is correct
7	Correct	10 ms	16724 KB	Output is correct
8	Correct	9 ms	16724 KB	Output is correct
9	Correct	9 ms	16812 KB	Output is correct
10	Correct	9 ms	16724 KB	Output is correct
11	Correct	9 ms	16724 KB	Output is correct
12	Correct	9 ms	16812 KB	Output is correct
13	Correct	9 ms	16808 KB	Output is correct
14	Correct	9 ms	16724 KB	Output is correct
15	Correct	9 ms	16816 KB	Output is correct
16	Correct	9 ms	16724 KB	Output is correct
17	Correct	9 ms	16724 KB	Output is correct
18	Correct	9 ms	16724 KB	Output is correct
19	Correct	10 ms	16812 KB	Output is correct
20	Correct	9 ms	16808 KB	Output is correct
21	Correct	10 ms	16748 KB	Output is correct
22	Correct	11 ms	16760 KB	Output is correct
23	Correct	9 ms	16816 KB	Output is correct
24	Correct	11 ms	16724 KB	Output is correct
25	Correct	9 ms	16772 KB	Output is correct
26	Correct	9 ms	16852 KB	Output is correct
27	Correct	10 ms	16808 KB	Output is correct
28	Correct	10 ms	16852 KB	Output is correct
29	Correct	9 ms	16852 KB	Output is correct
30	Correct	9 ms	16748 KB	Output is correct
31	Correct	10 ms	16852 KB	Output is correct
32	Correct	10 ms	16960 KB	Output is correct
33	Correct	12 ms	16980 KB	Output is correct
34	Correct	11 ms	17108 KB	Output is correct
35	Correct	11 ms	17108 KB	Output is correct
36	Correct	11 ms	17108 KB	Output is correct
37	Correct	12 ms	17200 KB	Output is correct
38	Correct	12 ms	17236 KB	Output is correct
39	Correct	11 ms	17236 KB	Output is correct
40	Correct	10 ms	17108 KB	Output is correct
41	Correct	11 ms	17084 KB	Output is correct
42	Correct	12 ms	17180 KB	Output is correct
43	Correct	12 ms	17236 KB	Output is correct
44	Correct	12 ms	17236 KB	Output is correct
45	Correct	12 ms	17236 KB	Output is correct
46	Correct	14 ms	17464 KB	Output is correct
47	Correct	12 ms	17360 KB	Output is correct
48	Correct	11 ms	17236 KB	Output is correct
49	Correct	12 ms	17364 KB	Output is correct
50	Correct	11 ms	17232 KB	Output is correct
51	Correct	12 ms	17208 KB	Output is correct
52	Correct	11 ms	17364 KB	Output is correct
53	Correct	12 ms	17364 KB	Output is correct
54	Correct	12 ms	17364 KB	Output is correct
55	Correct	17 ms	18036 KB	Output is correct
56	Correct	33 ms	21664 KB	Output is correct
57	Correct	51 ms	24484 KB	Output is correct
58	Correct	71 ms	26820 KB	Output is correct
59	Correct	89 ms	29688 KB	Output is correct
60	Correct	112 ms	35076 KB	Output is correct
61	Correct	133 ms	37952 KB	Output is correct
62	Correct	141 ms	39988 KB	Output is correct
63	Correct	177 ms	44580 KB	Output is correct
64	Correct	185 ms	45848 KB	Output is correct
65	Correct	88 ms	39272 KB	Output is correct
66	Correct	91 ms	39224 KB	Output is correct
67	Correct	88 ms	39212 KB	Output is correct
68	Correct	155 ms	43280 KB	Output is correct
69	Correct	175 ms	43596 KB	Output is correct
70	Correct	172 ms	43480 KB	Output is correct
71	Correct	206 ms	58124 KB	Output is correct
72	Correct	204 ms	58608 KB	Output is correct
73	Correct	181 ms	54576 KB	Output is correct
74	Correct	186 ms	54580 KB	Output is correct
75	Correct	185 ms	53492 KB	Output is correct
76	Correct	183 ms	53520 KB	Output is correct
77	Correct	198 ms	52988 KB	Output is correct
78	Correct	217 ms	53376 KB	Output is correct
79	Correct	192 ms	50204 KB	Output is correct

Submission #544684

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 29.0 / 29.0

Subtask #4 45.0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
29.0 / 29.0

Subtask #4
45.0 / 45.0