oj.uz

Submission #1084156

# Submission time Handle Problem Language Result Execution time Memory
1084156 2024-09-05T12:26:59 Z De3b0o Jobs (BOI24_jobs) C++17
14 / 100
 2000 ms 147884 KB 
#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;
ll vis[300009];

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});
    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,1e18,0,it);
        for(auto it : v)
        {
            if(vis[it])
                return -1;
            vis[it]=1;
            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;
        ll es = 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];
        }
        for(auto itt : o[ln])
        {
            if(-itt.F.F>s)
            {
                sx.erase(itt);
            }
            else
            {
                se.erase({itt.F.S,itt.S});
            }
        }
        s+=es;
        while(!sx.empty())
        {
            auto it = sx.end();
            it--;
            if(-it->F.F>s)
                break;
            se.in({it->F.S,it->S});
            sx.erase(it);
        }
    }
    cout << s-os;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 59580 KB Output is correct
2 Correct 576 ms 53588 KB Output is correct
3 Correct 273 ms 47060 KB Output is correct
4 Incorrect 210 ms 50476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14544 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 11 ms 14684 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 35 ms 18756 KB Output is correct
7 Correct 20 ms 16472 KB Output is correct
8 Correct 9 ms 14940 KB Output is correct
9 Correct 8 ms 14700 KB Output is correct
10 Correct 7 ms 14696 KB Output is correct
11 Correct 8 ms 14808 KB Output is correct
12 Correct 9 ms 15004 KB Output is correct
13 Correct 19 ms 16476 KB Output is correct
14 Correct 8 ms 14912 KB Output is correct
15 Correct 7 ms 14684 KB Output is correct
16 Correct 7 ms 14684 KB Output is correct
17 Correct 8 ms 14936 KB Output is correct
18 Correct 13 ms 15708 KB Output is correct
19 Correct 16 ms 16040 KB Output is correct
20 Correct 8 ms 14680 KB Output is correct
21 Correct 7 ms 14680 KB Output is correct
22 Correct 7 ms 14684 KB Output is correct
23 Correct 7 ms 14840 KB Output is correct
24 Correct 9 ms 14680 KB Output is correct
25 Correct 9 ms 14940 KB Output is correct
26 Correct 7 ms 14684 KB Output is correct
27 Correct 7 ms 14684 KB Output is correct
28 Correct 32 ms 18528 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14544 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 11 ms 14684 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 35 ms 18756 KB Output is correct
7 Correct 20 ms 16472 KB Output is correct
8 Correct 9 ms 14940 KB Output is correct
9 Correct 8 ms 14700 KB Output is correct
10 Correct 7 ms 14696 KB Output is correct
11 Correct 8 ms 14808 KB Output is correct
12 Correct 9 ms 15004 KB Output is correct
13 Correct 19 ms 16476 KB Output is correct
14 Correct 8 ms 14912 KB Output is correct
15 Correct 7 ms 14684 KB Output is correct
16 Correct 7 ms 14684 KB Output is correct
17 Correct 8 ms 14936 KB Output is correct
18 Correct 13 ms 15708 KB Output is correct
19 Correct 16 ms 16040 KB Output is correct
20 Correct 8 ms 14680 KB Output is correct
21 Correct 7 ms 14680 KB Output is correct
22 Correct 7 ms 14684 KB Output is correct
23 Correct 7 ms 14840 KB Output is correct
24 Correct 9 ms 14680 KB Output is correct
25 Correct 9 ms 14940 KB Output is correct
26 Correct 7 ms 14684 KB Output is correct
27 Correct 7 ms 14684 KB Output is correct
28 Correct 32 ms 18528 KB Output is correct
29 Execution timed out 2063 ms 147884 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14544 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 11 ms 14684 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 35 ms 18756 KB Output is correct
7 Correct 20 ms 16472 KB Output is correct
8 Correct 9 ms 14940 KB Output is correct
9 Correct 8 ms 14700 KB Output is correct
10 Correct 7 ms 14696 KB Output is correct
11 Correct 8 ms 14808 KB Output is correct
12 Correct 9 ms 15004 KB Output is correct
13 Correct 19 ms 16476 KB Output is correct
14 Correct 8 ms 14912 KB Output is correct
15 Correct 7 ms 14684 KB Output is correct
16 Correct 7 ms 14684 KB Output is correct
17 Correct 8 ms 14936 KB Output is correct
18 Correct 13 ms 15708 KB Output is correct
19 Correct 16 ms 16040 KB Output is correct
20 Correct 8 ms 14680 KB Output is correct
21 Correct 7 ms 14680 KB Output is correct
22 Correct 7 ms 14684 KB Output is correct
23 Correct 7 ms 14840 KB Output is correct
24 Correct 9 ms 14680 KB Output is correct
25 Correct 9 ms 14940 KB Output is correct
26 Correct 7 ms 14684 KB Output is correct
27 Correct 7 ms 14684 KB Output is correct
28 Correct 32 ms 18528 KB Output is correct
29 Correct 6 ms 14424 KB Output is correct
30 Correct 8 ms 14684 KB Output is correct
31 Correct 7 ms 14836 KB Output is correct
32 Correct 8 ms 14680 KB Output is correct
33 Incorrect 7 ms 14684 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 59580 KB Output is correct
2 Correct 576 ms 53588 KB Output is correct
3 Correct 273 ms 47060 KB Output is correct
4 Incorrect 210 ms 50476 KB Output isn't correct
5 Halted 0 ms 0 KB -