Submission #1051139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051139		GusterGoose27	Jobs (BOI24_jobs)	C++17	69 / 100	104 ms	37712 KiB

Main

#include <bits/stdc++.h>

#define sz(s) (int)s.size()

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;

typedef array<ll, 2> ar2;

void shift(int v, vector<ar2> &profit) {
	vector<ar2> nxt;
	ll oval = 0;
	// if (v == 0) {
	// 	cerr << "HERE";
	// }
	for (ar2 a: profit) {
		if (a[0] <= v) {
			oval = max(oval, a[1]);
		}
		else {
			if (oval != -1) {
				nxt.push_back({0, max(0ll, v+oval)});
				oval = -1;
			}
			if (a[1]+v > 0) nxt.push_back({a[0]-v, a[1]+v});
		}
	}
	if (oval != -1) nxt.push_back({0, max(0ll, v+oval)});
	profit = nxt;
}

ll nxt_pos(ll pos, int ind, vector<ar2> &vals, ll ex) {
	if (ind == sz(vals)-1) return inf;
	return vals[ind+1][0]-ex;
}

void move_up(ll pos, int &l, int &r, vector<ar2> &a, vector<ar2> &b) {
	bool f = 1;
	while (f) {
		f = 0;
		if (pos >= nxt_pos(pos, r, b, a[l][1])) {
			r++;
			f = 1;
		}
		if (pos >= nxt_pos(pos, l, a, b[r][1])) {
			l++;
			f = 1;
		}
	}
}

vector<ar2> merge(vector<ar2> &a, vector<ar2> &b) {
	vector<ar2> ans;
	int l = 0, r = 0;
	ll pos = 0;
	while (1) {
		move_up(pos, l, r, a, b);
		ans.push_back({pos, a[l][1]+b[r][1]});
		if (l+r == sz(a) + sz(b) - 2) break;
		pos = min(nxt_pos(pos, l, a, b[r][1]),
			nxt_pos(pos, r, b, a[l][1]));
	}
	return ans;
}

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 priority_queue<ar2, vector<ar2>, greater<ar2>> pq;
ll pval[MAXN];

void make_prof(pq &prof, int cur, ll sm = 0, ll mn = 0) {
	sm += val[cur];
	mn = min(mn, sm);
	if (sm > 0) {
		prof.push({-mn, cur});
		pval[cur] = sm;
		return;
	}
	if (!nxt[cur].empty()) make_prof(prof, nxt[cur][0], sm, mn);
}

void solve2() {
	pq prof;
	for (int rt: rts) {
		make_prof(prof, rt);
	}
	ll o = s;
	while (!prof.empty()) {
		ar2 t = prof.top();
		prof.pop();
		if (s < t[0]) break;
		s += pval[t[1]];
		if (!nxt[t[1]].empty()) make_prof(prof, nxt[t[1]][0]);
	}
	cout << s-o << '\n';
}

void print(vector<ar2> &v) {
	for (ar2 a: v) {
		cout << a[0] << ',' << a[1] << " - ";
	}
	cout << '\n';
}

vector<ar2> builddp(int cur) {
	vector<ar2> ans({{0, 0}});
	for (int v: nxt[cur]) {
		vector<ar2> cur = builddp(v);
		ans = merge(ans, cur);
	}
	shift(val[cur], ans);
	// print(ans);
	return ans;
}

void solve3() {
	vector<ar2> ans({{0, 0}});
	for (int rt: rts) {
		vector<ar2> cur = builddp(rt);
		ans = merge(ans, cur);
	}
	int ind = upper_bound(ans.begin(), ans.end(), ar2({s, inf}))-ans.begin();
	assert(ind);
	cout << ans[ind-1][1] << '\n';
}

bool chk_nxt() {
	for (int i = 0; i < n; i++) {
		if (sz(nxt[i]) > 1) return 0;
	}
	return 1;
}

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) solve3();
	else if (chk_nxt()) solve2();
	else assert(false);
}

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