oj.uz

Submission #958234

# Submission time Handle Problem Language Result Execution time Memory
958234 2024-04-05T08:19:28 Z IBory Fireworks (APIO16_fireworks) C++17
0 / 100
 5 ms 23132 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAX = 300003;
ll Z[MAX], W[MAX], off[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]);
			swap(off[cur], off[next]);
		}

		if (!PQ[next].empty()) {
			ll a = PQ[cur].top() + off[cur]; PQ[cur].pop();
			ll b = PQ[cur].top() + off[cur]; PQ[cur].push(a - off[cur]);
			ll c = PQ[next].top() + off[next]; PQ[next].pop();
			ll d = PQ[next].top() + off[next]; PQ[next].push(c - off[next]);
			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 + off[next] - off[cur]);
		}
	}

	ll t = 0LL;
	if (!PQ[cur].empty()) {
		ll p = PQ[cur].top(); PQ[cur].pop();
		t = p - PQ[cur].top();
	}
	off[cur] += W[cur];
	ll m = (PQ[cur].empty() ? 0LL : PQ[cur].top());
	PQ[cur].push(m - W[cur]);
	PQ[cur].push(m + t);
	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;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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