제출 #1102995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102995		hqminhuwu	Jobs (BOI24_jobs)	C++14	54 / 100	122 ms	36592 KiB

Main

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
	bool minz(X &x, const Y &y) {
		if (x > y) {
			x = y;
			return true;
		} return false;
	}
template<class X, class Y>
	bool maxz(X &x, const Y &y) {
		if (x < y) {
			x = y;
			return true;
		} return false;
	}

const int N = 5e5 + 5;
const ll oo = (ll) 1e18;
const ll mod = 1e9 + 7; // 998244353;

ll ans, p[N], f[N], w[N], dp[N], del[N], s, n;
vector <int> a[N];

ll dfs1 (int u){
	ll tmp = w[u];
	
	for (int v : a[u])
		tmp += dfs1(v);

	return max(0ll, tmp);
}

stack <int> st;

void dfs (int u){
	f[u] += w[u];
	
	if (ans + s + f[u] < 0){
		return;
	}

	dp[u] = w[u];
	st.push(u);

	for (int v : a[u]){
		if (del[v]) continue;
		f[v] = f[u];
		dfs(v);
		dp[u] += dp[v];
	}

	if (dp[u] < 0){
		dp[u] = 0;
		while (st.top() != u){
			st.pop();
		}
		st.pop();
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef kaguya
		freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> s;

	forr (i, 1, n){
		cin >> w[i] >> p[i];
		a[p[i]].pb(i);
	}

	if (s == oo){
		forr (i, 1, n)
		if (!p[i]){
			ans += dfs1(i);
		}

		cout << ans << "\n";
	} else if (n <= 5000){
		forr (t, 1, n){
			forr (i, 1, n){
				dp[i] = f[i] = 0;
			}

			forr (i, 1, n){
				if (!p[i] && !del[i]){
					dfs(i);

					while (st.size()){
						int u = st.top();
						st.pop();
						del[u] = 1;
						ans += w[u];
						for (int v : a[u]){
							p[v] = 0;
						}
					}
				}
			}
		}

		cout << ans << "\n";
	} 

	return 0;
}
/*



*/

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