Submission #1045105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045105		owoovo	Jobs (BOI24_jobs)	C++17	11 / 100	140 ms	47044 KiB

Main

#include <bits/stdc++.h>
#define ll __int128_t
#define pqi priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
#define F first
#define S second
using namespace std;
const ll maxn=1e18;
long long  n,s,pp[300010],p[300010];
vector<int> e[300010];
pqi dfs(int now){
    pqi pq;
    for(auto x:e[now]){
        pqi pq2=dfs(x);
        if(pq.size()<pq2.size())swap(pq,pq2);
        while(!pq2.empty()){
            pq.push(pq2.top());
            pq2.pop();
        }
    }
    ll need=max(0ll,-pp[now]),pf=pp[now];
    while(!pq.empty()&&pf<=0){
        auto [x,y]=pq.top();
        pf+=y;
        need=max(need,x-pf);
        pq.pop();
    }
    while(!pq.empty()&&pq.top().F<=need+pf){
        pf+=pq.top().S;
        pq.pop();
    }
    assert(pf>0||pq.empty());
    if(pf>0)pq.push({need,pf});
    return pq;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        long long a,b;
        cin>>a>>b;
        pp[i]=a;
        p[i]=b;
        e[b].push_back(i);
    }
    pqi pq=dfs(0);
    ll now=s,pf=0;
    while(!pq.empty()&&now+pf>=pq.top().F){
        //auto [x,y]=pq.top();
        //cout<<x<<" "<<y<<' '<<"?\n";
        pf+=pq.top().S;
        pq.pop();
    }
    cout<<(long long)(pf)<<"\n";
    return 0;
}

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