Submission #1084030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084030		De3b0o	Jobs (BOI24_jobs)	C++17	0 / 100	136 ms	31672 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];
ll vis[300009];
vector<pair<pll,ll>> o[300009];
multiset<pair<pll,ll>> se;

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(!v.empty())
    {
        for(auto it : v)
        {
            for(auto itt : o[it])
            {
                auto ittt = se.find(itt);
                se.erase(ittt);
            }
            o[it].clear();
        }
        for(auto it : v)
            dfs(it,0,0,it);
        for(auto it : v)
        {
            for(auto itt : o[it])
            {
                se.in(itt);
            }
        }
        v.clear();
        if(se.empty())
            break;
        auto itt = se.end();
        itt--;
        if(-itt->F.F>s)
            break;
        if(itt->F.S<0)
            break;
        s+=itt->F.S;
        ll nd = itt->S;
        while(vis[nd]==0&&nd!=0)
        {
            vis[nd]=1;
            for(auto it : adj[nd])
            {
                p[it]=0;
                if(vis[it]==0)
                    v.pb(it);
            }
            nd=p[nd];
        }
    }
    cout << s-os;
}

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