oj.uz

Submission #958269

# Submission time Handle Problem Language Result Execution time Memory
958269 2024-04-05T09:18:18 Z IBory Fireworks (APIO16_fireworks) C++17
0 / 100
 5 ms 21084 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 4 ms 21080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Incorrect 4 ms 21080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 4 ms 21080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 4 ms 21080 KB Output isn't correct
3 Halted 0 ms 0 KB -