Submission #1052746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052746		Nonoze	Jobs (BOI24_jobs)	C++17	43 / 100	2029 ms	46676 KiB

Main

/*
*	Author: Nonoze
*	Created: Sunday 05/05/2024
*/
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
#define int long long


#ifndef _IN_LOCAL
	#define dbg(...) ;
#endif
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) {cout << x << endl; return;}
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}



struct Segtree {
	int n;
	vector<int> tree, values;
	vector<pair<int, int>> lazy;
	Segtree(int _n) {
		n = _n;
		tree.resize(4*n, -inf);
		values.resize(4*n, -inf);
		lazy.resize(4*n, {-1, inf});
	}
	void build(vector<pair<int, int>> &a) {
		build(a, 1, 0, n-1);
	}
	void build(vector<pair<int, int>> &a, int v, int l, int r) {
		if (l == r) {
			tree[v] = a[l].fi;
			values[v] = a[l].se;
			return;
		}
		int m = (l+r)/2;
		build(a, 2*v, l, m);
		build(a, 2*v+1, m+1, r);
		int ans=-inf;
		if (l!=m || values[2*v]>=0) cmax(ans, tree[2*v]);
		if (m+1!=r || values[2*v+1]>=0) cmax(ans, tree[2*v+1]);
		tree[v] = ans;
	}
	void push(int v, int l, int r) {
		if (lazy[v].fi == -1) return;
		tree[v] += lazy[v].fi; cmin(tree[v], lazy[v].se);
		if (l != r) {
			if (lazy[2*v].fi == -1) lazy[2*v].fi = 0;
			if (lazy[2*v+1].fi == -1) lazy[2*v+1].fi = 0;
			lazy[2*v].fi += lazy[v].fi;
			lazy[2*v+1].fi += lazy[v].fi;
			cmin(lazy[2*v].se, lazy[v].se);
			cmin(lazy[2*v+1].se, lazy[v].se);
		}
		lazy[v] = {-1, inf};
	}
	void update(int v, int l, int r, int ql, int qr, pair<int, int> val, int val2) {
		push(v, l, r);
		if (l > qr || r < ql) return;
		if (l >= ql && r <= qr) {
			if (val.fi==-inf) {
				tree[v] = val.se;
				return;
			}
			if (val2!=-inf) values[v] = val2;
			lazy[v] = val;
			push(v, l, r);
			return;
		}
		int m = (l+r)/2;
		update(2*v, l, m, ql, qr, val, val2);
		update(2*v+1, m+1, r, ql, qr, val, val2);
		int ans=-inf;
		if (l!=m || values[2*v]>=0) cmax(ans, tree[2*v]);
		if (m+1!=r || values[2*v+1]>=0) cmax(ans, tree[2*v+1]);
		tree[v] = ans;
	}
	void update(int l, int r, int val, int val2, int val3) {
		update(1, 0, n-1, l, r, {val, val2}, val3);
	}
	int query(int v, int l, int r, int required) {
		push(v, l, r);
		if (required + tree[v] < 0) return -1;
		if (l == r) return l;
		int m = (l+r)/2;
		push(2*v, l, m); push(2*v+1, m+1, r);
		cout << l << " " << r << " " << tree[v] << " " << values[v] << endl;
		if (l==m && values[2*v]<0) return query(2*v+1, m+1, r, required);
		if (m+1==r && values[2*v+1]<0) return query(2*v, l, m, required);
		if (tree[2*v]>tree[2*v+1]) return query(2*v, l, m, required);
		return query(2*v+1, m+1, r, required);
	}
	int query(int required) {
		return query(1, 0, n-1, required);
	}
	int que(int v, int l, int r, int empl) {
		push(v, l, r);
		if (l == r) return tree[v];
		int m = (l+r)/2;
		if (empl <= m) return que(2*v, l, m, empl);
		return que(2*v+1, m+1, r, empl);
	}
	int que(int empl) {
		return que(1, 0, n-1, empl);
	}
};

int n, k, leftt;
vector<int> a, p, minii, pref, in, out;
vector<set<int>> adj;
int comp=0;

void dfsmini(int i, int sum, int mini) {
	sum+=a[i]; cmin(mini, sum); minii[i]=mini; pref[i]=sum;
	in[i]=comp++;
	for (auto u: adj[i]) dfsmini(u, sum, mini);
	out[i]=comp++;
}

pair<pair<int, int>, int> dfs(int i, int sum, int mini) {
	sum+=a[i]; cmin(mini, sum);
	if (sum >= 0 && i) return {{mini, sum}, i};
	vector<pair<pair<int, int>, int>> res;
	for (auto u: adj[i]) {
		auto temp=dfs(u, sum, mini);
		if (temp.se!=-1) res.pb(temp);
	}
	if (res.empty()) return {{-1, -1}, -1};
	sort(rall(res));
	return res[0];
}


void solve() {
	cin >> n >> k; n++;
	a.resize(n), p.resize(n), adj.resize(n), minii.resize(n, 0), in.resize(n), out.resize(n), pref.resize(n);
	for (int i=1; i<n; i++) {
		cin >> a[i] >> p[i];
		adj[p[i]].insert(i);
	}
	dfsmini(0, 0, 0);
	for (int tt=0; tt<n; tt++) {
		for (int i=1; i<n; i++) {
			if (a[i]>=0 && minii[p[i]]+k>=0) {
				a[p[i]]+=a[i];
				adj[p[i]].erase(i);
				for (auto u: adj[i]) {
					adj[p[i]].insert(u);
					p[u]=p[i];
				}
				adj[i].clear();
				a[i]=-inf;
				dfsmini(0, 0, 0);
			}
		}
	}
	// vector<pair<int, int>> tobuild(comp, {-inf, -inf});
	// map<int, int> mp;
	// for (int i=1; i<n; i++) {
	// 	tobuild[in[i]]={minii[i], pref[i]};
	// 	tobuild[out[i]]={minii[i], pref[i]};
	// 	mp[in[i]]=i;
	// 	mp[out[i]]=i;
	// }
	// Segtree seg(comp); seg.build(tobuild);
	// for (int t=0; t<n; t++) {
	// 	int i=seg.query(k);
	// 	cout << i << " " << mp[i] << " " << pref[mp[i]] << endl;
	// 	if (i==-1) break;
	// 	i=mp[i];
	// 	if (a[i]>=0) {
	// 		a[p[i]]+=a[i];
	// 		adj[p[i]].erase(i);
	// 		for (auto u: adj[i]) {
	// 			adj[p[i]].insert(u);
	// 			p[u]=p[i];
	// 		}
	// 		adj[i].clear();
	// 		int mini=0;
	// 		if (p[i]!=0) mini=seg.que(in[p[i]]);
	// 		seg.update(in[p[i]], in[i]-1, a[i], mini, -inf);
	// 		seg.update(out[i]+1, out[p[i]], a[i], mini, -inf);
	// 		seg.update(in[p[i]], in[p[i]], -inf, seg.que(in[p[i]]), a[p[i]]);
	// 		seg.update(out[p[i]], out[p[i]], -inf, seg.que(out[p[i]]), a[p[i]]);
	// 		a[i]=-inf;
	// 	}
	// 	seg.update(in[i], in[i], -inf, -inf, -inf);
	// 	seg.update(out[i], out[i], -inf, -inf, -inf);
	// }
	leftt=k+a[0]; a[0]=0;
	int sum=0, mini=0;
	auto base=dfs(0, 0, 0);
	while (base.se != -1 && leftt + base.fi.fi >= 0) {
		int i = base.se;
		sum=0; int par=i;
		vector<int> begining;
		while (par != 0) {
			sum += a[par];
			adj[p[par]].erase(par);
			for (auto u: adj[par]) p[u]=0, adj[0].insert(u);
			adj[par].clear();
			par = p[par];
		}
		if (sum<0) break;
		leftt += sum;
		base=dfs(0, 0, 0);
	}
	cout << leftt-k << endl;
	return;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:226:13: warning: unused variable 'mini' [-Wunused-variable]
  226 |  int sum=0, mini=0;
      |             ^~~~

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