Submission #39868

#	Time	Username	Problem	Language	Result	Execution time	Memory
39868		cheater2k	Fireworks (APIO16_fireworks)	C++14	100 / 100	270 ms	52464 KiB

fireworks

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

const int N = 300005;

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

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

void debug(slope &s) {
	priority_queue <long long> tmp = s.pq;
	vector<long long> 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]
			long long 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]);

			long long x1 = S[i].pq.top(); S[i].pq.pop(); // x-coordinate at slope 1
			long long 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()) {
			long long x = S[i].pq.top(); S[i].pq.pop();
			S[par].pq.push(x);
		}
	}

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

	vector<long long> 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 += starting_slope * (pts[i] - pts[i-1]);
		++starting_slope;
		ans = min(ans, starting_value);
	}

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

Compilation message (stderr)

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 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45