Submission #1113438

#TimeUsernameProblemLanguageResultExecution timeMemory
1113438vjudge1Jobs (BOI24_jobs)C++17
100 / 100
337 ms87160 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define szz(r) (ll)r.size() #define vi vector<int> #define vvi vector<vi> #define pp pair<ll,int> #define ub(x,i) upper_bound(all(x),i)-x.begin() using namespace std; const int mxn=3e5+5; vector<int>g[mxn]; ll x[mxn]{0}; multiset<pii>ms[mxn]; void dfs(int u){ for(auto v:g[u]){ dfs(v); if(ms[u].size()<ms[v].size())swap(ms[u],ms[v]); for(auto it:ms[v])ms[u].insert(it); } ll st=max(-x[u],1ll*0),pf=x[u]; if(st==0)ms[u].insert({st,pf}); else { while(pf<0&&!ms[u].empty()){ auto it = ms[u].begin(); st = max(st,it->f-pf); pf+=it->s;ms[u].erase(it); } if(pf>=0){ while(!ms[u].empty()){ auto it=ms[u].begin(); if(it->f<=st)pf+=it->s,ms[u].erase(it); else break; }ms[u].insert({st,pf}); } } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll n,s;cin>>n>>s; for(int i=1;i<=n;i++){ int p;cin>>x[i]>>p; g[p].pb(i); }dfs(0); ll rs=0; for(auto it : ms[0])if(rs+s>=it.f)rs+=it.s; cout<<rs; }
#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...