Submission #1057088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057088		0npata	Jobs (BOI24_jobs)	C++17	0 / 100	114 ms	52052 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];
const int INF = 1e17;

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 = x[u];
	int money = INF;
	int total_gain = x[u];
	int extra = 0;

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

//	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);

	cout << thr[0][0]-1 << '\n';
}

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