이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
#define int ll
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, ll>> 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()){
auto g = *dd.rbegin();
if(g.ff + s < 0) break;
//cout<<s<<'\n';
//for(auto h: dd){
// cout<<h.ff<<' '<<h.ss<<'\n';
//}
s += a[g.ss];
dd.erase(dd.find(g));
er(g.ss);
ans += a[g.ss];
}
cout<<ans<<'\n';
}
signed main(){
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |