제출 #1025472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025472		pcc	Jobs (BOI24_jobs)	C++17	0 / 100	252 ms	61244 KiB

Main

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

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const ll mxn = 3e5+10;
ll N,S;
ll arr[mxn];
vector<int> tree[mxn],tree2[mxn],tree3[mxn];
vector<int> rts;
ll dp[mxn];
ll mn[mxn];
priority_queue<pll,vector<pll>,less<pll>> son[mxn];

void dfs(int now,int top = 0){
	dp[top] += arr[now];
	for(auto nxt:tree[now]){
		mn[nxt] = min(mn[now],arr[nxt]);
		if(arr[nxt]<0){
			tree2[top].push_back(nxt);
			dfs(nxt,nxt);
		}
		else{
			dfs(nxt,top);
		}
	}
}

void dfs2(int now){
	for(auto nxt:tree2[now]){
		dfs2(nxt);
		//cerr<<"TREE2: "<<now<<','<<nxt<<':'<<arr[nxt]<<' '<<dp[nxt]<<endl;
		son[now].push(pll(dp[nxt],nxt));
	}
	ll tmp = arr[now];
	while(dp[now]<=0&&!son[now].empty()){
		auto id = son[now].top().sc;
		son[now].pop();
		if(dp[id]<0)continue;
		dp[now] += dp[id];
		arr[now] = min(arr[now],tmp+arr[id]);
		int sh = arr[id];
		if(son[now].size()<son[id].size()){
			son[now].swap(son[id]);
			sh = -sh;
		}
		while(!son[id].empty()){
			auto [dep,nxt] = son[id].top();son[id].pop();
			son[now].push(pll(dep+arr[nxt]+sh,nxt));
		}
	}
	while(!son[now].empty()){
		tree3[now].push_back(son[now].top().sc);
		son[now].pop();
	}
	return;
}


void dfs3(int now){
	//cerr<<now<<":"<<arr[now]<<','<<dp[now]<<endl;
	for(auto nxt:tree3[now]){
		//cerr<<now<<','<<nxt<<endl;
		dfs3(nxt);
	}
	return;
}

priority_queue<pll,vector<pll>,less<pll>> pq;
int main(){
	cin>>N>>S;
	for(int i = 1;i<=N;i++){
		ll x,p;
		cin>>x>>p;
		tree[p].push_back(i);
		arr[i] = x;
	}
	dfs(0,0);
	//cerr<<"DFS1 DONE!"<<endl;
	dfs2(0);
	//cerr<<"DFS2 DONE!"<<endl;
	pq.push(pll(arr[0],0));
	ll ans = 0;
	while(!pq.empty()&&S+pq.top().fs>=0){
		auto [val,id] = pq.top();pq.pop();
		if(dp[id]<0)continue;
		ans += dp[id];
		S += dp[id];
		for(auto nxt:tree3[id]){
			pq.push(pll(arr[nxt],nxt));
		}
	}
	dfs3(0);
	cout<<ans<<'\n';
	return 0;
}

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