Submission #1263348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263348		vidux	Jobs (BOI24_jobs)	C++17	14 / 100	2096 ms	28484 KiB

Main

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

typedef long long ll;
typedef unsigned long long ull; 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

#define FOR(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define REP(i, k, n) for (int(i) = (k); (i) <= (n); ++(i))
#define REPR(i, k, n) for (int(i) = (k); (i) >= (n); --(i))
#define FORR(x, arr) for (auto &x : arr)
#define FORR2(x, y, arr) for (auto &[x, y] : arr)
#define ALL(a) (a.begin()), (a.end())
#define RALL(a) (a.rbegin()), (a.rend())
#define REVERSE(v) reverse(ALL(v))
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << (x) << endl

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LLINF = 1e18;

void solve() {
	ll n, s; cin >> n >> s;
	vl p(n), x(n);
	vvi adj(n);
	FOR(i, n) {
		cin >> x[i] >> p[i];
		p[i]--;
		if (p[i] >= 0) adj[p[i]].push_back(i);
	}
	vl need(n), rew(n);
	vi alive(n, 1), seen(n);
	auto dfs = [&](auto dfs, ll c, int u, int p = -1) -> void {
		if (!alive[u] || seen[u]) return;
		seen[u] = 1;
		c += x[u];
		rew[u] = c;
		need[u] = min(need[u], c);
		if (p >= 0) need[u] = min(need[u], need[p]);
		FORR(v, adj[u]) dfs(dfs, c, v, u);
	};
	ll ans = 0;
	while (1) {
		fill(ALL(seen), 0);
		fill(ALL(need), 0);
		fill(ALL(rew), 0);
		FOR(i, n) if (alive[i]) dfs(dfs, 0, i);
		ll prof = 0, u = -1;
		FOR(i, n) if (alive[i] && s+need[i] >= 0) {
			if (prof < rew[i]) {
				prof = rew[i];
				u = i;
			}
		}
		if (prof == 0) break;
		while (u >= 0) {
			alive[u] = 0;
			u = p[u];
		}
		ans += prof;
		if (prof >= LLINF-s) s = LLINF;
		else s += prof;
	}
	cout << ans << endl;
	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

#if SINGLE_TEST
	solve();
#else
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
#endif

	return 0;
}

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