Submission #1051059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051059		GusterGoose27	Jobs (BOI24_jobs)	C++17	11 / 100	54 ms	23632 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5+5;
typedef long long ll;
const ll inf = 1e18;
int n;
vector<int> nxt[MAXN];
ll val[MAXN];
ll mx_val[MAXN];
vector<int> rts;
ll s;

ll dfs(int cur) {
	ll res = 0;
	for (int v: nxt[cur]) {
		res += dfs(v);
	}
	return max(0ll,res+val[cur]);
}

void solve1() {
	ll ans = 0;
	for (int i: rts) ans += dfs(i);
	cout << ans << '\n';
}

typedef array<ll, 2> ar2;

void make_prof(vector<ar2> &prof, int cur, ll sm = 0, ll mn = 0, ll mx = 0) {
	sm += val[cur];
	mn = min(mn, sm);
	if (sm > mx) {
		prof.push_back({-mn, sm-mx});
		mx = sm;
	}
	if (!nxt[cur].empty()) make_prof(prof, nxt[cur][0], sm, mn, mx);
}

void solve2() {
	vector<ar2> prof;
	for (int rt: rts) {
		make_prof(prof, rt);
	}
	sort(prof.begin(), prof.end());
	ll o = s;
	for (ar2 a: prof) {
		if (s < a[0]) break;
		s += a[1];
	}
	cout << s-o << '\n';
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		int p; cin >> val[i] >> p;
		if (p == 0) rts.push_back(i);
		else nxt[p-1].push_back(i);
	}
	if (s == inf) solve1();
	else if (n <= 2000) solve2();
	else assert(false);
}

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