Submission #1086545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086545		IBory	Jobs (BOI24_jobs)	C++17	0 / 100	2070 ms	26452 KiB

Main

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 300003;
vector<int> G[MAX];
ll S[MAX], P[MAX], V[MAX];

pii DFS(int cur, int prev, ll lim, ll down, ll up) {
	pii ret = {-1, cur};
	if (!V[cur] && down <= lim) ret = max(ret, pii{up, cur});
	for (int next : G[cur]) {
		if (next == prev) continue;
		ret = max(ret, DFS(next, cur, lim, min(down, up + S[next]), up + S[next]));
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll N, init;
	cin >> N >> init;
	for (int i = 1; i <= N; ++i) {
		cin >> S[i] >> P[i];
		G[P[i]].push_back(i);
	}

	V[0] = 1;
	ll ans = init, cnt = 0;
	while (1) {
		pii go = DFS(0, 0, ans, 0, S[0]);
		if (go.first < 0) break;

		ans += go.first;
		int cur = go.second;
		while (cur && !V[cur]) {
			V[cur] = 1;
			S[cur] = 0;
			cur = P[cur];
		}
	}

	cout << ans - init;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:17: warning: unused variable 'cnt' [-Wunused-variable]
   30 |  ll ans = init, cnt = 0;
      |                 ^~~

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