답안 #39867 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39867	2018-01-22T14:38:39 Z	cheater2k	Fireworks (APIO16_fireworks)	C++14	26 / 100	10 ms	18428 KB

fireworks

#include <bits/stdc++.h>
using namespace std;

const int N = 300005;

struct slope {
	priority_queue <int> pq;
	long long starting_value;
	int starting_slope;
} S[N];

int n, m, p[N], a[N];
long long ans;

void debug(slope &s) {
	priority_queue <int> tmp = s.pq;
	vector<int> ret;
	while(tmp.size()) {
		ret.push_back(tmp.top()); tmp.pop();
	}
	reverse(ret.begin(), ret.end());

	cerr << "DEBUG\n";
	cerr << "starting value = " << s.starting_value << " starting_slope = " << s.starting_slope << endl;
	cerr << "[ "; for (auto c : ret) cerr << c << ' '; cerr << " ]\n";
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 2; i <= n + m; ++i) {
		scanf("%d %d", &p[i], &a[i]);
		if (i >= n + 1) { // leaf
			S[i].pq.push(a[i]); S[i].pq.push(a[i]); // -x + a and x - a
			S[i].starting_slope = -1;
			S[i].starting_value = a[i]; // -0 + a
		}
	}

	for (int i = n + m; i >= 2; --i) {
		if (i <= n) { // not leaf
			// fix slopes of S[i]
			int last_slope = S[i].starting_slope + S[i].pq.size();
			while(last_slope > 1) {
				S[i].pq.pop(); --last_slope;
			}
			//cerr << i << ' '; debug(S[i]);

			int x1 = S[i].pq.top(); S[i].pq.pop(); // x-coordinate at slope 1
			int x0 = S[i].pq.top(); S[i].pq.pop(); // x-coordinate at slope 0

			S[i].starting_value += a[i];
			S[i].pq.push(x0 + a[i]);
			S[i].pq.push(x1 + a[i]);

			//cerr << i << ' '; debug(S[i]);
		}

		// update to p[i]
		int par = p[i];
		if (S[par].pq.size() < S[i].pq.size()) {
			swap(S[par], S[i]);
		}
		S[par].starting_value += S[i].starting_value;
		S[par].starting_slope += S[i].starting_slope;
		while(!S[i].pq.empty()) {
			int x = S[i].pq.top(); S[i].pq.pop();
			S[par].pq.push(x);
		}
	}

	// root: 1
	long long starting_value = S[1].starting_value;
	int starting_slope = S[1].starting_slope;

	vector<int> pts;

	while(!S[1].pq.empty()) {
		pts.push_back(S[1].pq.top()); S[1].pq.pop();
	}
	pts.push_back(0);
	reverse(pts.begin(), pts.end());

	ans = starting_value;
	for (int i = 1; i < pts.size(); ++i) {
		starting_value += 1LL * starting_slope * (pts[i] - pts[i-1]);
		++starting_slope;
		ans = min(ans, starting_value);
	}

	printf("%lld\n", ans);
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < pts.size(); ++i) {
                    ^
fireworks.cpp:29:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
fireworks.cpp:31:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p[i], &a[i]);
                               ^

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	18428 KB	Output is correct
2	Correct	0 ms	18428 KB	Output is correct
3	Correct	5 ms	18428 KB	Output is correct
4	Correct	3 ms	18428 KB	Output is correct
5	Correct	10 ms	18428 KB	Output is correct
6	Correct	5 ms	18428 KB	Output is correct
7	Correct	0 ms	18428 KB	Output is correct
8	Correct	6 ms	18428 KB	Output is correct
9	Correct	2 ms	18428 KB	Output is correct
10	Correct	0 ms	18428 KB	Output is correct

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	18428 KB	Output is correct
2	Correct	4 ms	18428 KB	Output is correct
3	Correct	2 ms	18428 KB	Output is correct
4	Correct	7 ms	18428 KB	Output is correct
5	Correct	6 ms	18428 KB	Output is correct
6	Correct	2 ms	18428 KB	Output is correct
7	Correct	0 ms	18428 KB	Output is correct
8	Correct	8 ms	18428 KB	Output is correct
9	Correct	0 ms	18428 KB	Output is correct
10	Correct	3 ms	18428 KB	Output is correct
11	Correct	0 ms	18428 KB	Output is correct
12	Correct	3 ms	18428 KB	Output is correct
13	Correct	5 ms	18428 KB	Output is correct
14	Correct	1 ms	18428 KB	Output is correct
15	Correct	0 ms	18428 KB	Output is correct
16	Correct	6 ms	18428 KB	Output is correct
17	Correct	3 ms	18428 KB	Output is correct
18	Correct	2 ms	18428 KB	Output is correct
19	Correct	0 ms	18428 KB	Output is correct

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	18428 KB	Output is correct
2	Correct	0 ms	18428 KB	Output is correct
3	Correct	5 ms	18428 KB	Output is correct
4	Correct	3 ms	18428 KB	Output is correct
5	Correct	10 ms	18428 KB	Output is correct
6	Correct	5 ms	18428 KB	Output is correct
7	Correct	0 ms	18428 KB	Output is correct
8	Correct	6 ms	18428 KB	Output is correct
9	Correct	2 ms	18428 KB	Output is correct
10	Correct	0 ms	18428 KB	Output is correct
11	Correct	0 ms	18428 KB	Output is correct
12	Correct	4 ms	18428 KB	Output is correct
13	Correct	2 ms	18428 KB	Output is correct
14	Correct	7 ms	18428 KB	Output is correct
15	Correct	6 ms	18428 KB	Output is correct
16	Correct	2 ms	18428 KB	Output is correct
17	Correct	0 ms	18428 KB	Output is correct
18	Correct	8 ms	18428 KB	Output is correct
19	Correct	0 ms	18428 KB	Output is correct
20	Correct	3 ms	18428 KB	Output is correct
21	Correct	0 ms	18428 KB	Output is correct
22	Correct	3 ms	18428 KB	Output is correct
23	Correct	5 ms	18428 KB	Output is correct
24	Correct	1 ms	18428 KB	Output is correct
25	Correct	0 ms	18428 KB	Output is correct
26	Correct	6 ms	18428 KB	Output is correct
27	Correct	3 ms	18428 KB	Output is correct
28	Correct	2 ms	18428 KB	Output is correct
29	Correct	0 ms	18428 KB	Output is correct
30	Incorrect	2 ms	18428 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	18428 KB	Output is correct
2	Correct	0 ms	18428 KB	Output is correct
3	Correct	5 ms	18428 KB	Output is correct
4	Correct	3 ms	18428 KB	Output is correct
5	Correct	10 ms	18428 KB	Output is correct
6	Correct	5 ms	18428 KB	Output is correct
7	Correct	0 ms	18428 KB	Output is correct
8	Correct	6 ms	18428 KB	Output is correct
9	Correct	2 ms	18428 KB	Output is correct
10	Correct	0 ms	18428 KB	Output is correct
11	Correct	0 ms	18428 KB	Output is correct
12	Correct	4 ms	18428 KB	Output is correct
13	Correct	2 ms	18428 KB	Output is correct
14	Correct	7 ms	18428 KB	Output is correct
15	Correct	6 ms	18428 KB	Output is correct
16	Correct	2 ms	18428 KB	Output is correct
17	Correct	0 ms	18428 KB	Output is correct
18	Correct	8 ms	18428 KB	Output is correct
19	Correct	0 ms	18428 KB	Output is correct
20	Correct	3 ms	18428 KB	Output is correct
21	Correct	0 ms	18428 KB	Output is correct
22	Correct	3 ms	18428 KB	Output is correct
23	Correct	5 ms	18428 KB	Output is correct
24	Correct	1 ms	18428 KB	Output is correct
25	Correct	0 ms	18428 KB	Output is correct
26	Correct	6 ms	18428 KB	Output is correct
27	Correct	3 ms	18428 KB	Output is correct
28	Correct	2 ms	18428 KB	Output is correct
29	Correct	0 ms	18428 KB	Output is correct
30	Incorrect	2 ms	18428 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #39867

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