Submission #1084039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084039		De3b0o	Jobs (BOI24_jobs)	C++17	29 / 100	258 ms	40252 KiB

Main

#include<bits/stdc++.h>
#include<random>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define sq 547

using namespace std;

ll n , s;
ll a[300009] , p[300009];
vector<ll> adj[300009];
vector<pair<pll,ll>> o[300009];
set<pll> se;
set<pair<pll,ll>> sx;

void dfs(ll x , ll mn , ll sum , ll op)
{
    sum+=a[x];
    mn=min(mn,sum);
    if(sum>=0)
    {
        o[op].pb({{mn,sum},x});
        return;
    }
    for(auto it : adj[x])
        dfs(it,mn,sum,op);
}

int main()
{
    cin >> n >> s;
    ll os = s;
    for(int i = 1 ; n>=i ; i++)
    {
        cin >> a[i] >> p[i];
        adj[p[i]].pb(i);
    }
    vector<ll> v;
    for(int i = 1 ; n>=i ; i++)
    {
        if(p[i]==0)
            v.pb(i);
    }
    while(true)
    {
        for(auto it : v)
            dfs(it,0,0,it);
        for(auto it : v)
        {
            for(auto itt : o[it])
            {
                if(-itt.F.F>s)
                {
                    sx.in(itt);
                }
                else
                {
                    se.in({itt.F.S,itt.S});
                }
            }
        }
        v.clear();
        if(se.empty())
            break;
        auto itt = se.end();
        itt--;
        if(itt->F<0)
            break;
        s+=itt->F;
        ll nd = itt->S;
        ll ln = -1;
        while(nd!=0)
        {
            for(auto it : adj[nd])
            {
                if(it!=ln)
                {
                    p[it]=0;
                    v.pb(it);
                }
            }
            ln=nd;
            nd=p[nd];
        }
        while(!sx.empty())
        {
            auto it = sx.end();
            it--;
            if(-it->F.F>s)
                break;
            se.in({it->F.S,it->S});
            sx.erase(it);
        }
        for(auto itt : o[ln])
        {
            if(-itt.F.F>s)
            {
                sx.erase(itt);
            }
            else
            {
                se.erase({itt.F.S,itt.S});
            }
        }
    }
    cout << s-os;
}

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