oj.uz

Submission #994939

# Submission time Handle Problem Language Result Execution time Memory
994939 2024-06-08T08:42:51 Z hmm789 Jobs (BOI24_jobs) C++14
11 / 100
 203 ms 52332 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 

vector<int> adj[300005];
int a[300005];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> v[300005];

void dfs(int x) {
	for(int i : adj[x]) {
		dfs(i);
		if(v[i].size() > v[x].size()) swap(v[i], v[x]);
		while(v[i].size()) {
			v[x].push(v[i].top());
			v[i].pop();
		}
	}
	if(a[x] >= 0) v[x].push({0, a[x]});
	else {
		pair<int, int> cur = {-a[x], a[x]};
		while(v[x].size() && cur.second < 0) {
			pair<int, int> tmp = v[x].top();
			v[x].pop();
			cur.first = max(cur.first, cur.second-tmp.first);
			cur.second += tmp.second;
		}
		if(cur.second >= 0) v[x].push(cur);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, s, x, ans = 0;
	cin >> n >> s;
	a[0] = s;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> x;
		adj[x].push_back(i);
	}
	dfs(0);
	while(v[0].size() && v[0].top().first <= ans) {
		ans += v[0].top().second;
		v[0].pop();
	}
	cout << ans-s;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 49224 KB Output is correct
2 Correct 144 ms 39872 KB Output is correct
3 Correct 108 ms 33940 KB Output is correct
4 Correct 98 ms 41408 KB Output is correct
5 Correct 88 ms 48348 KB Output is correct
6 Correct 89 ms 37260 KB Output is correct
7 Correct 178 ms 44712 KB Output is correct
8 Correct 111 ms 34808 KB Output is correct
9 Correct 79 ms 44804 KB Output is correct
10 Correct 85 ms 49416 KB Output is correct
11 Correct 185 ms 52332 KB Output is correct
12 Correct 139 ms 42948 KB Output is correct
13 Correct 203 ms 47652 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Incorrect 4 ms 19548 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Incorrect 4 ms 19548 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Incorrect 4 ms 19548 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 49224 KB Output is correct
2 Correct 144 ms 39872 KB Output is correct
3 Correct 108 ms 33940 KB Output is correct
4 Correct 98 ms 41408 KB Output is correct
5 Correct 88 ms 48348 KB Output is correct
6 Correct 89 ms 37260 KB Output is correct
7 Correct 178 ms 44712 KB Output is correct
8 Correct 111 ms 34808 KB Output is correct
9 Correct 79 ms 44804 KB Output is correct
10 Correct 85 ms 49416 KB Output is correct
11 Correct 185 ms 52332 KB Output is correct
12 Correct 139 ms 42948 KB Output is correct
13 Correct 203 ms 47652 KB Output is correct
14 Correct 3 ms 19032 KB Output is correct
15 Correct 3 ms 19036 KB Output is correct
16 Correct 3 ms 19036 KB Output is correct
17 Correct 3 ms 19292 KB Output is correct
18 Incorrect 4 ms 19548 KB Output isn't correct
19 Halted 0 ms 0 KB -