제출 #1029242

#제출 시각아이디문제언어결과실행 시간메모리
1029242OtalpJobs (BOI24_jobs)C++14
0 / 100
1004 ms919216 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pb push_back #define ff first #define ss second vector<int> q[300100]; ll a[300100]; ll dp[300100][2]; ll kto[300100]; int us[300100]; int p[300100]; ll pref[300100]; ll ddp[300100]; vector<pair<ll, ll>> d[300100]; void dfs(int v, int p){ dp[v][0] = a[v]; dp[v][1] = 0; for(int to: q[v]){ if(to == p) continue; dfs(to, v); dp[v][0] += dp[to][0]; dp[v][1] += dp[to][1]; } if(dp[v][1] > dp[v][0]) kto[v] = 0; else kto[v] = 1; dp[v][1] = min(dp[v][1], dp[v][0]); } void dfs2(int v, int P, int k, ll sum){ if(k == 1){ k = kto[v]; } pref[v] = sum; us[v] = k; p[v] = P; sum += a[v]; for(int to: q[v]){ if(to == P) continue; dfs2(to, v, k, sum); } } void dfs3(int v, int p){ ddp[v] = -1e18; if(a[v] >= 0) ddp[v] = pref[v]; d[v].pb({pref[v], a[v]}); for(int to: q[v]){ if(to == p) continue; dfs3(to, v); for(pair<ll, ll> h: d[to]){ if(h.ss + a[v] >= 0){ ddp[v] = max(ddp[v], min(pref[v], h.ff)); } d[v].pb({min(pref[v], h.ff), h.ss + a[v]}); } } } set<pair<ll, int>> dd; void er(int v){ for(int to: q[v]){ if(to == p[v]) continue; dd.insert({ddp[to] - pref[to], to}); } } void solve(){ ll n, s; cin>>n>>s; ll ans = s; for(int i=1; i<=n; i++){ int l, r; cin>>l>>r; q[r].pb(i); q[i].pb(r); a[i] = l; ans += a[i]; } dfs(0, -1); dfs2(0, -1, 1, 0); ans = 0; dfs3(0, -1); dd.insert({ddp[0], 0}); while(dd.size()){ pii g = *dd.rbegin(); if(g.ff > s) break; dd.erase(dd.find(g)); er(g.ss); ans += a[g.ss]; } cout<<ans; } signed main(){ solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...