Submission #1113438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113438		vjudge1	Jobs (BOI24_jobs)	C++17	100 / 100	337 ms	87160 KiB

Main

#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;
}

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