Submission #994609

#	Time	Username	Problem	Language	Result	Execution time	Memory
994609		pavement	Jobs (BOI24_jobs)	C++17	14 / 100	2068 ms	27504 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back

using ll = long long;

int N, idx, rv[300005], pre[300005], sz[300005], x[300005], p[300005];
ll s, os, wei[300005], mn[300005];
bool seen[300005];
vector<int> adj[300005];

int dfs(int u) {
	wei[u] += x[u];
	mn[u] = min(mn[u], wei[u]);
	pre[u] = idx++;
	rv[idx] = u;
	sz[u] = 1;
	for (auto v : adj[u]) {
		wei[v] = wei[u];
		mn[v] = min(mn[v], mn[u]);
		sz[u] += dfs(v);
	}
	return sz[u];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> s;
	os = s;
	for (int i = 1; i <= N; i++) {
		cin >> x[i] >> p[i];
		adj[p[i]].pb(i);
	}
	seen[0] = 1;
	while (1) {
		for (int i = 1; i <= N; i++) {
			mn[i] = LLONG_MAX;
		}
		dfs(0);
		pair<ll, int> tk = mp(-1, -1);
		for (int i = 1; i <= N; i++) {
			if (!seen[i] && s + mn[i] >= 0) {
				tk = max(tk, mp(wei[i], i));
			}
		}
		if (tk.first < 0) {
			break;
		}
		s += tk.first;
		for (int j = tk.second; !seen[j]; j = p[j]) {
			seen[j] = 1;
			x[j] = 0;
		}
	}
	cout << s - os << '\n';
}

• Subtask 1: 0 / 11
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31