oj.uz

Submission #994932

# Submission time Handle Problem Language Result Execution time Memory
994932 2024-06-08T08:38:06 Z pavement Jobs (BOI24_jobs) C++17
11 / 100
 192 ms 49224 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back

using ll = long long;
using ill = pair<int, ll>;

int N, x[300005];
ll s, profit;
vector<int> adj[300005];
priority_queue<ill, vector<ill>, greater<ill> > pq[300005];

void print(priority_queue<ill, vector<ill>, greater<ill> > tmp) {
	while (!tmp.empty()) {
		auto [r, p] = tmp.top();
		cout << r << ' ' << p << '\n';
		tmp.pop();
	}
}

void dfs(int u) {
	for (auto v : adj[u]) {
		dfs(v);
		if (pq[u].size() < pq[v].size()) {
			swap(pq[u], pq[v]);
		}
		while (!pq[v].empty()) {
			pq[u].push(pq[v].top());
			pq[v].pop();
		}
	}
	if (x[u] >= 0) {
		pq[u].emplace(0, x[u]);
	} else {
		int r = -x[u], p = x[u];
		while (!pq[u].empty() && r >= pq[u].top().first) {
			p += pq[u].top().second;
			pq[u].pop();
		}
		while (!pq[u].empty() && p < 0) {
			auto [nr, np] = pq[u].top();
			r = max(r, nr - p);
			p += np;
			pq[u].pop();
		}
		if (p >= 0) {
			pq[u].emplace(r, p);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> s;
	for (int i = 1, p; i <= N; i++) {
		cin >> x[i] >> p;
		adj[p].pb(i);
	}
	dfs(0);
	while (!pq[0].empty() && s >= pq[0].top().first) {
		s += pq[0].top().second;
		profit += pq[0].top().second;
		pq[0].pop();
	}
	cout << profit << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 47944 KB Output is correct
2 Correct 128 ms 38660 KB Output is correct
3 Correct 104 ms 34120 KB Output is correct
4 Correct 91 ms 38592 KB Output is correct
5 Correct 112 ms 44748 KB Output is correct
6 Correct 91 ms 35576 KB Output is correct
7 Correct 156 ms 42196 KB Output is correct
8 Correct 111 ms 33092 KB Output is correct
9 Correct 77 ms 41480 KB Output is correct
10 Correct 79 ms 45384 KB Output is correct
11 Correct 192 ms 49224 KB Output is correct
12 Correct 143 ms 41264 KB Output is correct
13 Correct 161 ms 46148 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 17240 KB Output is correct
6 Correct 3 ms 17240 KB Output is correct
7 Correct 3 ms 17012 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 17008 KB Output is correct
10 Incorrect 3 ms 17076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 17240 KB Output is correct
6 Correct 3 ms 17240 KB Output is correct
7 Correct 3 ms 17012 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 17008 KB Output is correct
10 Incorrect 3 ms 17076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 17240 KB Output is correct
6 Correct 3 ms 17240 KB Output is correct
7 Correct 3 ms 17012 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 17008 KB Output is correct
10 Incorrect 3 ms 17076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 47944 KB Output is correct
2 Correct 128 ms 38660 KB Output is correct
3 Correct 104 ms 34120 KB Output is correct
4 Correct 91 ms 38592 KB Output is correct
5 Correct 112 ms 44748 KB Output is correct
6 Correct 91 ms 35576 KB Output is correct
7 Correct 156 ms 42196 KB Output is correct
8 Correct 111 ms 33092 KB Output is correct
9 Correct 77 ms 41480 KB Output is correct
10 Correct 79 ms 45384 KB Output is correct
11 Correct 192 ms 49224 KB Output is correct
12 Correct 143 ms 41264 KB Output is correct
13 Correct 161 ms 46148 KB Output is correct
14 Correct 3 ms 16984 KB Output is correct
15 Correct 3 ms 16984 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 17240 KB Output is correct
19 Correct 3 ms 17240 KB Output is correct
20 Correct 3 ms 17012 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 17008 KB Output is correct
23 Incorrect 3 ms 17076 KB Output isn't correct
24 Halted 0 ms 0 KB -