제출 #1053090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053090		vjudge1	Jobs (BOI24_jobs)	C++17	29 / 100	210 ms	31568 KiB

Main

#include <iostream>
#include <vector>
#include <set>

using namespace std;
#define int long long
const int N = 3e5 + 10;
vector<int> vec[N];
int pr[N], erased[N], nxt[N];

set<pair<int,pair<int,int>>> st;

void dfs(int u, int sum = 0, int mx = 0){
	if (erased[u])
		return;

	sum += pr[u];
	if (sum >= 0){
		st.insert({mx, {sum, u}});
		return;
	}
	mx = max(mx, -sum);

	for (int i : vec[u])
		dfs(i, sum, mx);
}

signed main(){
	int n, s;
	cin>>n>>s;
	int init = s;
	for (int i=1, dp;i<=n;i++){
		cin>>pr[i]>>dp;
		vec[dp].push_back(i);
		nxt[i] = dp;
	}

	st.insert({0, {0, 0}});

	while (st.size() > 0){
		auto [req, p] = *begin(st);
		auto [prft, ind] = p;
		if (req > s)
			break;
		
		st.erase(begin(st));
		if (erased[ind])
			continue;
		s += prft;

		while (!erased[ind]){
			erased[ind] = 1;
			for (int i : vec[ind])
				dfs(i);
			ind = nxt[ind];
		}
	}

	cout<<s - init<<'\n';

}

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