Submission #1312034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312034		ppmn_6	Jobs (BOI24_jobs)	C++20	14 / 100	2095 ms	26136 KiB

Main

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n, s;
    cin >> n >> s;
    ll ss = s;
    vector<vector<ll>> graph(n);
    vector<ll> x(n), p(n);
    for (ll i = 0; i < n; i++) {
		cin >> x[i] >> p[i];
		p[i]--;
		if (p[i] != -1) {
			graph[p[i]].push_back(i);
		}
	}
	// {low, net}
	vector<pair<ll, ll>> res(n);
	auto dfs = [&] (auto self, ll c, ll low, ll net)->void {
		net += x[c];
		low = min(low, net);
		res[c] = {low, net};
		for (auto &v : graph[c]) {
			self(self, v, low, net);
		}
	};
	for (ll i = 0; i < n; i++) {
		if (p[i] == -1) {
			dfs(dfs, i, 0, 0);
		}
	}
	vector<bool> vis(n, 0);
	while (true) {
		ll best = 0, id = -1;
		for (ll i = 0; i < n; i++) {
			if (res[i].first + s >= 0 && res[i].second > best && !vis[i]) {
				id = i;
				best = res[i].second;
			}
		}
		if (!best) {
			break;
		}
		ll u = id;
		stack<ll> stk;
		stk.push(u);
		while (p[u] != -1 && !vis[p[u]]) {
			u = p[u];
			stk.push(u);
		}
		while (stk.size()) {
			u = stk.top();
			stk.pop();
			vis[u] = 1;
			for (auto &v : graph[u]) {
				if (stk.empty() || v != stk.top()) {
					dfs(dfs, v, 0, 0);
				}
			}
			s += x[u];
		}
	}
	cout << s - ss;
	
    return 0;
}

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