Submission #1085929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085929		vjudge1	Jobs (BOI24_jobs)	C++17	0 / 100	118 ms	24792 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pb push_back
#define umap unordered_map
#define mset multiset
#define pq priority_queue
const int maxn=3e5+10;
struct node{
	int u,w;
	bool operator <(node _) const{
		return w<_.w;
	}
};
int n,s,val[maxn],in[maxn],dp[maxn];
vector<int> g[maxn];
pq<node> q;
void solve(){
	cin>>n>>s;
	for(int i=1,x;i<=n;i++){
		cin>>val[i]>>x;
		if(x) g[x].pb(i),in[i]++;
	}
	int res=s;
	for(int i=1;i<=n;i++) if(!in[i]) q.push({i,val[i]});
	while(q.size()){
		int u=q.top().u,w=q.top().w;
		q.pop();
		if(s+w<0) continue;
		s+=w,res=max(res,s);
		for(int v:g[u]){
			in[v]--;
			if(!in[v]) q.push({v,val[v]});
		}
	}
	cout<<res<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--) solve();
	return 0;
}
/*
Samples
input:

output:

THINGS TODO:
检查freopen，尤其是后缀名
检查空间
检查调试语句是否全部注释
*/

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