Submission #1147958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147958		vulestamenkovic	Jobs (BOI24_jobs)	C++20	0 / 100	135 ms	29656 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define MAXN (int)4e5+5
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
bool vis[MAXN];
vector<int> g[MAXN];
int n,s,e[MAXN];
class ll {
public:
	bool u=0;
	int v=0,m=0;
	vector<ll*> a;
	ll(){
		u=0;v=0;m=0;
	};
};
void dfs(int x,ll*a,int v,int m){
	vis[x]=1;
	v+=e[x];
	m=min(v,m);
	if(v>0){
		a->v=v;a->u=1;a->m=m;
		a->a.push_back(new ll());
		for(int&y:g[x]){
			if(!vis[y]){
				dfs(y,a->a[a->a.size()-1],0,0);
			}
		}
	}else{
		for(int&y:g[x]){
			if(!vis[y]){
				dfs(y,a,v,m);
			}
		}
	}
}
void solve() {
	cin>>n>>s;
	stack<int>d;
	for(int i=1;i<=n;i++){int p;
		cin>>e[i]>>p;
		if(!p){
			d.push(i);
			continue;
		}
		g[p].push_back(i);
	}
	priority_queue<pair<int,ll*>>pq;
	while(!d.empty()){
		ll* x=new ll();
		dfs(d.top(),x,0,0);
		d.pop();
		if(x!=nullptr&&x->u){
			pq.emplace(x->m,x);
		}
	}int os=s;
	while(!pq.empty()){
		ll* x=pq.top().se;pq.pop();
		if(s<x->m){
			break;
		}
		for(ll*b:x->a){
			if(b!=nullptr&&b->u){
				pq.emplace(b->m,b);
			}
		}
		s+=x->v;
	}
	cout<<s-os<<'\n';
}
int32_t main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int32_t T=1;//cin>>T;
	while(T--) {
		solve();
	}
	return 0;
}

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