Submission #1057407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057407		0npata	Jobs (BOI24_jobs)	C++17	43 / 100	2057 ms	941140 KiB

Main

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

#define int long long
#define vec vector

const int MXN = 300'005;

vec<int> tree[MXN];
map<int, int> thr[MXN];
int x[MXN];

void dfs(int u) {
	map<int, int> ch_thrs;
	for(int v : tree[u]) {
		dfs(v);
		for(auto [t, g] : thr[v]) {
			ch_thrs[t] += g;
		}
	}

	//int money = 1e17;
	int money = x[u];
	int total_gain = x[u];
	int extra = 0;

	int total_gain_prev = 0;
	if(total_gain > 0) {
		thr[u][extra] = total_gain;
		//total_gain = 0;
	}
	for(auto [t, g] : ch_thrs) {
		if(money >= t) {
			money += g;
			total_gain += g;
		}
		else {
			if(total_gain > 0) {
				total_gain_prev += total_gain;
				total_gain = 0;
			}
			extra += t-money;
			money = t;
			total_gain += g;
			money += g;
		}
		if(total_gain > 0) {
			thr[u][extra+total_gain_prev] = total_gain;
		}
	}

	if(false){
	cerr << u << ": ";
	for(auto [t, g] : thr[u]) {
		cerr << "(" << t << ", " << g << ") ";
	}
	cerr << '\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);

	int N, S;
	cin >> N >> S;
	N += 1;

	x[0] = S;

	for(int i = 1; i<N; i++) {
		cin >> x[i];
		int p;
		cin >> p;
		tree[p].push_back(i);
	}

	//cerr << "INPUT READ" << '\n';
	dfs(0);

	assert(thr[0][0] - S >= 0);
	cout << thr[0][0]-S << '\n';
}

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