Submission #47706

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
47706	2018-05-06T11:12:00 Z	square1001	Fireworks (APIO16_fireworks)	C++14	26 / 100	16 ms	14864 KB

fireworks

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
// Time complexity: possibly O(N+M log(N+M))
int N, M, p[300009], c[300009], id[300009]; vector<int> g[300009]; vector<long long> v[300009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	long long sum = 0;
	for (int i = 1; i < N + M; i++) {
		cin >> p[i] >> c[i];
		g[--p[i]].push_back(i);
		sum += c[i];
		if (i >= N) {
			v[i - N].push_back(c[i]);
			v[i - N].push_back(c[i]);
			id[i] = i - N;
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		int mx = 0;
		for (int j : g[i]) {
			if (mx < v[id[j]].size()) {
				mx = v[id[j]].size();
				id[i] = id[j];
			}
		}
		vector<int> dv = { 0, (int)v[id[i]].size() };
		for (int j : g[i]) {
			if (id[j] != id[i]) {
				v[id[i]].insert(v[id[i]].end(), v[id[j]].begin(), v[id[j]].end());
				dv.push_back(v[id[i]].size());
			}
		}
		int ds = dv.size() - 1;
		for (int j = 1; j < ds; j *= 2) {
			for (int k = 0; k < ds; k += j * 2) {
				if (k + j * 2 <= ds) {
					vector<int> pass(v[id[i]].begin() + dv[k + j], v[id[i]].begin() + dv[k + j * 2]);
					vector<int> tmp(dv[k + j * 2] - dv[k]);
					merge(v[id[i]].begin() + dv[k], v[id[i]].begin() + dv[k + j], pass.begin(), pass.end(), tmp.begin());
					copy(tmp.begin(), tmp.end(), v[id[i]].begin() + dv[k]);
				}
				else if (k + j < ds) {
					vector<int> pass(v[id[i]].begin() + dv[k + j], v[id[i]].end());
					vector<int> tmp(dv[ds] - dv[k]);
					merge(v[id[i]].begin() + dv[k], v[id[i]].begin() + dv[k + j], pass.begin(), pass.end(), tmp.begin());
					copy(tmp.begin(), tmp.end(), v[id[i]].begin() + dv[k]);
				}
			}
		}
		v[id[i]].resize(v[id[i]].size() - g[i].size() + 1);
		v[id[i]][v[id[i]].size() - 1] += c[i];
		v[id[i]][v[id[i]].size() - 2] += c[i];
	}
	for (int i = 0; i < v[id[0]].size(); i++) {
		sum -= (v[id[0]][i] - (i == 0 ? 0 : v[id[0]][i - 1])) * (v[id[0]].size() - i - 1);
	}
	cout << sum << '\n';
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:25:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (mx < v[id[j]].size()) {
        ~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[id[0]].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	14456 KB	Output is correct
2	Correct	13 ms	14456 KB	Output is correct
3	Correct	14 ms	14508 KB	Output is correct
4	Correct	13 ms	14584 KB	Output is correct
5	Correct	13 ms	14640 KB	Output is correct
6	Correct	13 ms	14680 KB	Output is correct
7	Correct	13 ms	14680 KB	Output is correct
8	Correct	14 ms	14692 KB	Output is correct
9	Correct	14 ms	14692 KB	Output is correct
10	Correct	12 ms	14692 KB	Output is correct

Subtask #2
19.0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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

Submission #47706

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 29.0

Subtask #4 0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 29.0

Subtask #4
0 / 45.0