Submission #1020055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020055		Tuanlinh123	Jobs (BOI24_jobs)	C++17	100 / 100	217 ms	78532 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=300005;
ll x[maxn], p[maxn];
vector <ll> A[maxn];
priority_queue <pll, vector <pll>, greater<pll>> S[maxn];

void dfs(ll u)
{
    for (ll v:A[u])
    {
        dfs(v);
        if (sz(S[v])>sz(S[u])) swap(S[u], S[v]);
        while (sz(S[v])) S[u].push(S[v].top()), S[v].pop();
    }
    if (x[u]>0) S[u].push({0, x[u]});
    else
    {
        ll sus=-x[u], Max=sus;
        while (sus>0 && sz(S[u]))
        {
            auto [c, v]=S[u].top(); S[u].pop();
            ll val=min(sus, v); 
            Max=max(Max, sus+c), sus-=val, v-=val;
            if (v) S[u].push({c, v});
        }
        ll sum=0;
        while (sz(S[u]) && S[u].top().fi<Max)
            sum+=S[u].top().se, S[u].pop();
        S[u].push({Max, sum});
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, s, ans=0; cin >> n >> s;
    for (ll i=1; i<=n; i++) 
        cin >> x[i] >> p[i], A[p[i]].pb(i);
    dfs(0);
    while (sz(S[0]))
    {
        auto [c, v]=S[0].top(); S[0].pop();
        if (s>=c) s+=v, ans+=v;
    }
    cout << ans;
}

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