Submission #958269

#	Time	Username	Problem	Language	Result	Execution time	Memory
958269		IBory	Fireworks (APIO16_fireworks)	C++17	0 / 100	5 ms	21084 KiB

fireworks

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

const int MAX = 300003;
ll Z[MAX], W[MAX], ans[MAX];
priority_queue<ll> PQ[MAX];
vector<int> G[MAX];

ll DFS(int cur) {
	ll& ret = Z[cur] = 1;
	for (int next : G[cur]) {
		ret += DFS(next);
		if (PQ[cur].size() < PQ[next].size()) {
			swap(PQ[cur], PQ[next]);
			swap(ans[cur], ans[next]);
		}

		if (!PQ[next].empty()) {
			ll a = PQ[cur].top(); PQ[cur].pop();
			ll b = PQ[cur].top(); PQ[cur].push(a);
			ll c = PQ[next].top(); PQ[next].pop();
			ll d = PQ[next].top(); PQ[next].push(c);
			if (c < b) ans[cur] += b - c;
			else if (a < d) ans[cur] += d - a;
		}

		ans[cur] += ans[next];
		while (!PQ[next].empty()) {
			ll n = PQ[next].top(); PQ[next].pop();
			PQ[cur].push(n);
		}
		while (PQ[cur].size() > ret) PQ[cur].pop();
	}

	ll t = 0LL;
	if (!PQ[cur].empty()) {
		ll p = PQ[cur].top(); PQ[cur].pop();
		t = p - PQ[cur].top();
	}

	ll m = (PQ[cur].empty() ? 0LL : PQ[cur].top());
	PQ[cur].push(m + W[cur]);
	PQ[cur].push(PQ[cur].top() + t);
	while (PQ[cur].size() > ret + 1) PQ[cur].pop();
	
	// cout << "Slope: " << cur << ' ' << ans[cur] << endl;
	// vector<ll> temp;
	// while (!PQ[cur].empty()) {
	// 	ll n = PQ[cur].top(); PQ[cur].pop();
	// 	temp.push_back(n);
	// 	cout << n << ' ';
	// }
	// cout << '\n' << '\n';
	// for (ll n : temp) PQ[cur].push(n);

	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	N += M;
	for (int i = 2; i <= N; ++i) {
		int a, b;
		cin >> a >> b;
		W[i] = b;
		G[a].push_back(i);
	}

	DFS(1);
	cout << ans[1];
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'll DFS(int)':
fireworks.cpp:33:25: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   33 |   while (PQ[cur].size() > ret) PQ[cur].pop();
      |          ~~~~~~~~~~~~~~~^~~~~
fireworks.cpp:45:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   45 |  while (PQ[cur].size() > ret + 1) PQ[cur].pop();
      |         ~~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45