제출 #1053076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053076		Jawad_Akbar_JJ	Jobs (BOI24_jobs)	C++17	29 / 100	186 ms	31580 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, bool St = 1){
	if (erased[u] and !St)
		return;
	mx = max(mx, -sum);
	if (!St){
		if (sum + pr[u] >= 0){
			st.insert({mx, {sum + pr[u], u}});
			return;
		}
		sum += pr[u];
	}
	for (int i : vec[u])
		dfs(i, sum, mx, 0);
}

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;
		if (erased[ind])
			continue;
		s += prft;
		st.erase(begin(st));

		while (!erased[ind]){
			erased[ind] = 1;
			dfs(ind);
			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