oj.uz

Submission #406746

# Submission time Handle Problem Language Result Execution time Memory
406746 2021-05-18T04:08:35 Z SeDunion Fireworks (APIO16_fireworks) C++17
7 / 100
 16 ms 23808 KB 
#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

ll ans;

vector<pair<int,int>>g[N];

priority_queue<ll>ql;
priority_queue<ll, vector<ll>, greater<ll>>qr;

pair<ll,ll> dfs(int v) {
	if (g[v].empty()) return {0, 0};
	vector<pair<ll,ll>>now;
	for (auto [to, c] : g[v]) {
		auto [nl, nr] = dfs(to);
		now.emplace_back(nl + c, nr + c);
	}
	while(ql.size())ql.pop();
	while(qr.size())qr.pop();
	for (auto [l, r] : now) {
		if (ql.empty() || qr.empty()) {
			assert(ql.empty() && qr.empty());
			ql.push(l);
			qr.push(r);
			continue;
		}
		ll L = ql.top(), R = qr.top();
		if (r <= L) {
			ql.push(l);
			ql.push(r);
			ans += ql.top() - r;
			qr.push(ql.top());
			ql.pop();
		} else if (l >= R) {
			qr.push(l);
			qr.push(r);
			ans += l - qr.top();
			ql.push(qr.top());
			qr.pop();
		} else {
			ql.push(l);
			qr.push(r);
		}
	}
	ll L = ql.top(), R = qr.top();
	return {L, R};
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 2 ; i <= n + m ; ++ i) {
		int p, c;
		cin >> p >> c;
		g[p].emplace_back(i, c);
	}
	dfs(1);
	cout << ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23736 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23804 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23728 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 14 ms 23756 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23796 KB Output is correct
2 Correct 13 ms 23728 KB Output is correct
3 Incorrect 13 ms 23800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23736 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23804 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23728 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 14 ms 23756 KB Output is correct
11 Correct 14 ms 23796 KB Output is correct
12 Correct 13 ms 23728 KB Output is correct
13 Incorrect 13 ms 23800 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 14 ms 23736 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23804 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23728 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 14 ms 23756 KB Output is correct
11 Correct 14 ms 23796 KB Output is correct
12 Correct 13 ms 23728 KB Output is correct
13 Incorrect 13 ms 23800 KB Output isn't correct
14 Halted 0 ms 0 KB -