Submission #1053127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053127		UmairAhmadMirza	Jobs (BOI24_jobs)	C++17	0 / 100	81 ms	36776 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=2e5+5;
int const mod=1e9+7;

int par[N],n,val[N];
vector<int> child[N];
vector<array<int,2>> tbl[N];

void dfs(int node){
	deque<array<int,2>> temp;
	for(int c:child[node]){
		dfs(c);
		for(array<int,2> p:tbl[c])
			temp.push_back(p);
		tbl[c].clear();
	}
	int r=max(0LL,-val[node]),pr=val[node];
	sort(temp.begin(), temp.end());
	deque<array<int,2>> v;
	while(temp.size()){
		if(temp[0][1]>0)
			v.push_back({max(temp[0][0],r),temp[0][1]});
		temp.pop_front();
	}
	// cout<<"node := "<<node<<endl;
	// cout<<r<<' '<<pr<<endl;
	if(v.size()){
		temp.push_back(v[0]);
		v.pop_front();
	}
	int i=0;
	for(array<int,2> p:v){
		if(temp[i][0]+temp[i][1]>=p[0])
			temp[i][1]+=p[1];
		else{
			temp.push_back(p);
			i++;
		}
	}
	v.clear();
	while(temp.size()){
		if(pr<0){
			pr+=temp[0][1];
			r=temp[0][0];
		}
		else
			break;
		temp.pop_front();
	}
	if(pr>0)
		temp.push_front({r,pr});
	sort(temp.begin(), temp.end());
	// cout<<temp.size()<<endl;
	v.clear();
	if(temp.size()){
		v.push_back(temp[0]);
		temp.pop_front();
	}
	i=0;
	for(array<int,2> p:temp){
		if(v[i][0]+v[i][1]>=p[0])
			v[i][1]+=p[1];
		else{
			v.push_back(p);
			i++;
		}
	}
	for(array<int,2> p:v){
		// cout<<p[0]<<' '<<p[1]<<endl;
		tbl[node].push_back(p); 
	}
}

signed main(){
	cin>>n;
	cin>>val[0];
	for (int i = 1; i <=n; ++i){
		cin>>val[i]>>par[i];
		child[par[i]].push_back(i);
	}
	dfs(0);
	int ans=-val[0];
	for (array<int,2> i:tbl[0])
		if(i[0]<=val[0])
			ans+=i[1];
	cout<<ans<<endl;
	return 0;
}

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