Submission #994682

#	Time	Username	Problem	Language	Result	Execution time	Memory
994682		pavement	Jobs (BOI24_jobs)	C++17	14 / 100	2060 ms	26772 KiB

Main

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

#define mp make_pair
#define pb push_back
#define int long long

using ll = long long;

int N, x[300005], p[300005];
ll ans, s, os, wei[300005], mn[300005];
bool seen[300005], reach[300005];
vector<int> adj[300005];

void dfs(int u) {
	wei[u] += x[u];
	reach[u] = 1;
	mn[u] = min(mn[u], wei[u]);
	for (auto v : adj[u]) {
		wei[v] = wei[u];
		mn[v] = mn[u];
		dfs(v);
	}
}

ll init(int u) {
	ll cur = 0;
	vector<int> new_adj;
	for (auto it = adj[u].begin(); it != adj[u].end(); ++it) {
		ll tmp = init(*it);
		if (tmp > 0) {
			new_adj.pb(*it);
			cur += tmp;
		}
	}
	swap(adj[u], new_adj);
	cur += x[u];
	return cur;
}

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);
	}
	init(0);
	seen[0] = 1;
	ans = s;
	while (1) {
		for (int i = 1; i <= N; i++) {
			mn[i] = 0;
		}
		dfs(0);
		pair<ll, int> tk = mp(LLONG_MIN, -1);
		for (int i = 1; i <= N; i++) {
			if (seen[i]) {
				assert(mn[i] == 0 && wei[i] == 0);
			}
			if (!seen[i] && reach[i] && s + mn[i] >= 0) {
				//~ cout << "OPTION " << i << '\n';
				tk = max(tk, mp(wei[i], i));
			}
		}
		if (tk.second == -1) {
			break;
		}
		//~ cout << "GO " << tk.second << '\n';
		s += tk.first;
		ans = max(ans, s);
		for (int j = tk.second; !seen[j]; j = p[j]) {
			seen[j] = 1;
			x[j] = 0;
		}
	}
	cout << ans - os << '\n';
}

Compilation message (stderr)

Main.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~

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