oj.uz

Submission #1064856

# Submission time Handle Problem Language Result Execution time Memory
1064856 2024-08-18T18:33:24 Z Boomyday Jobs (BOI24_jobs) C++17
43 / 100
 2000 ms 1048576 KB 
//
// Created by adavy on 8/18/2024.
//
#include <bits/stdc++.h>


using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

#define int ll

#define f first
#define s second

pair<ll,ll> merge(pair<ll,ll> a, pair<ll,ll> b){
    return {min(a.f,b.f),a.s-max(a.f,b.f)+b.s};
}


struct prs{
    set<pair<ll,ll>> ps;
    void insert(pair<ll,ll> p){
        /*
        cout << "ps: " << endl;
        for(auto& itm:ps){
            cout << itm.f << " " << itm.s << endl;
        }
        cout << "p: " << p.f << " " << p.s << endl;*/
        while(1){
            auto it = ps.lower_bound(p);
            if (it != ps.end()) {
                if (it-> f <= p.s){
                    p = merge(p,*it);
                    ps.erase(it);
                    continue;
                }
            }
            auto it2 = ps.upper_bound(p);
            if (it2 != ps.begin()){
                --it2;
                if (it2->s >= p.f){
                    p = merge(p,*it2);
                    ps.erase(it2);
                    continue;
                }
            }
            if (p.f > p.s){
                ps.clear();
                return;
            }
            ps.insert(p);

            break;
        }
    }
    void subtract(ll x){
        ll balance = -x;
        ll neg = balance;
        while (!ps.empty() && balance < 0){
            balance -= ps.begin()->f;
            neg = min(neg,balance);
            balance += ps.begin()->s;
            ps.erase(ps.begin());

        }
        if (balance >= 0){
            this->insert({-neg,balance-neg});
        }
    }
};

vector<vector<int>> adj;
vector<int> val;
vector<prs> sets;
vector<int> which;

void dfs(int v, int p){
    int maxsz = -1, maxch = -1;
    for(int u:adj[v]){
        if (u == p) continue;
        dfs(u,v);
        if (sets[u].ps.size() > maxsz){
            maxsz = sets[u].ps.size();
            maxch = u;
        }
    }
    if (maxsz == -1){
        which[v] = v;
    }
    else {
        which[v] = which[maxch];
    }
    for(int u:adj[v]){
        if (u==p || u == maxch) continue;
        for(auto& itm:sets[u].ps){
            sets[which[v]].insert(itm);
        }
    }
    if (val[v] > 0){
        sets[which[v]].insert({0LL,val[v]});
    }
    else {
        sets[which[v]].subtract(-val[v]);

    }
    // output v, sets[which[v]].ps

/*
    cout << "v: " << v << endl;
    for(auto& itm:sets[which[v]].ps){
      cout << itm.f << " " << itm.s << endl;
    }*/
}

signed main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int N,s; cin >> N >> s;
    adj.resize(N+1);
    val.resize(N+1);
    sets.resize(N+1);
    which.resize(N+1,-1);
    val[0] = 0;
    for(int i=1;i<=N;++i){
        ll x,p; cin >> x >> p;
        val[i] = x;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }
    dfs(0,-1);
    int t = s;
    for(auto& item:sets[which[0]].ps){
        if (t >= item.f){
            t -= item.f;
            t += item.s;
        }
    }
    cout << t-s << endl;





}

Compilation message

Main.cpp: In function 'void dfs(ll, ll)':
Main.cpp:84:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   84 |         if (sets[u].ps.size() > maxsz){
      |             ~~~~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1492 ms 477308 KB Output is correct
2 Correct 432 ms 103272 KB Output is correct
3 Correct 276 ms 65992 KB Output is correct
4 Execution timed out 2088 ms 812300 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 49 ms 22012 KB Output is correct
7 Correct 15 ms 8796 KB Output is correct
8 Correct 5 ms 1888 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 34 ms 15964 KB Output is correct
13 Correct 15 ms 8612 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 1372 KB Output is correct
18 Correct 20 ms 10420 KB Output is correct
19 Correct 15 ms 9052 KB Output is correct
20 Correct 3 ms 1884 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 3 ms 1884 KB Output is correct
24 Correct 15 ms 8068 KB Output is correct
25 Correct 14 ms 8252 KB Output is correct
26 Correct 3 ms 1880 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 49 ms 21596 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 49 ms 22012 KB Output is correct
7 Correct 15 ms 8796 KB Output is correct
8 Correct 5 ms 1888 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 34 ms 15964 KB Output is correct
13 Correct 15 ms 8612 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 1372 KB Output is correct
18 Correct 20 ms 10420 KB Output is correct
19 Correct 15 ms 9052 KB Output is correct
20 Correct 3 ms 1884 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 3 ms 1884 KB Output is correct
24 Correct 15 ms 8068 KB Output is correct
25 Correct 14 ms 8252 KB Output is correct
26 Correct 3 ms 1880 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 49 ms 21596 KB Output is correct
29 Correct 814 ms 516928 KB Output is correct
30 Correct 236 ms 94412 KB Output is correct
31 Correct 146 ms 57792 KB Output is correct
32 Correct 124 ms 98128 KB Output is correct
33 Execution timed out 2028 ms 1048576 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 49 ms 22012 KB Output is correct
7 Correct 15 ms 8796 KB Output is correct
8 Correct 5 ms 1888 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 34 ms 15964 KB Output is correct
13 Correct 15 ms 8612 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 1372 KB Output is correct
18 Correct 20 ms 10420 KB Output is correct
19 Correct 15 ms 9052 KB Output is correct
20 Correct 3 ms 1884 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 3 ms 1884 KB Output is correct
24 Correct 15 ms 8068 KB Output is correct
25 Correct 14 ms 8252 KB Output is correct
26 Correct 3 ms 1880 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 49 ms 21596 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 2 ms 1372 KB Output is correct
31 Correct 2 ms 1116 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 21 ms 11432 KB Output is correct
35 Correct 1 ms 860 KB Output is correct
36 Correct 3 ms 1884 KB Output is correct
37 Correct 2 ms 1116 KB Output is correct
38 Correct 1 ms 768 KB Output is correct
39 Correct 1 ms 860 KB Output is correct
40 Correct 11 ms 7004 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 3 ms 1884 KB Output is correct
43 Correct 2 ms 1116 KB Output is correct
44 Correct 1 ms 860 KB Output is correct
45 Correct 1 ms 664 KB Output is correct
46 Correct 10 ms 5724 KB Output is correct
47 Correct 1 ms 1116 KB Output is correct
48 Correct 3 ms 1372 KB Output is correct
49 Correct 2 ms 1372 KB Output is correct
50 Correct 1 ms 860 KB Output is correct
51 Correct 1 ms 860 KB Output is correct
52 Correct 3 ms 2140 KB Output is correct
53 Correct 2 ms 1372 KB Output is correct
54 Correct 2 ms 1372 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1492 ms 477308 KB Output is correct
2 Correct 432 ms 103272 KB Output is correct
3 Correct 276 ms 65992 KB Output is correct
4 Execution timed out 2088 ms 812300 KB Time limit exceeded
5 Halted 0 ms 0 KB -