oj.uz

Submission #39867

# Submission time Handle Problem Language Result Execution time Memory
39867 2018-01-22T14:38:39 Z cheater2k Fireworks (APIO16_fireworks) C++14
26 / 100
 10 ms 18428 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -