Submission #1259891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259891		kikitop1gg	Jobs (BOI24_jobs)	C++17	100 / 100	224 ms	55844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf INT_MAX

ll top_sort(ll v, vvi& g, vb& visited, vi& topSort, ll ind) {
    visited[v] = true;
    for(auto x : g[v]) {
        if(visited[x]) continue;
        ind = top_sort(x, g, visited, topSort, ind);
    }
    topSort[ind] = v;
    return ind - 1;
}

int main() {
    ifstream in("input.txt");
    ofstream out("output.txt");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll n, s;
    cin >> n >> s;
    vi val(n + 1, 0);
    vvi g(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> val[i];
        ll prev;
        cin >> prev;
        g[prev].push_back(i);
    }

    vi topSort(n + 1, -1);
    vb visited(n + 1, false);
    ll ind = n;
    for(int i = 0; i <= n; i++) {
        if(visited[i]) continue;
        ind = top_sort(i, g, visited, topSort, ind);
    }

    vector<multiset<pp>*> profit(n + 1);
    for(int i = n; i >= 0; i--) {
        ll v = topSort[i];
        ll req = max(0LL, -val[v]);
        ll biggest = -1;
        for(auto x : g[v]) {
            if(biggest == -1 || profit[x]->size() > profit[biggest]->size()) {
                biggest = x;
            }
        }
        if(biggest == -1 || profit[biggest]->size() == 0) {
            profit[v] = new multiset<pp>();
        }
        else {
            profit[v] = profit[biggest];
        }
        auto& cur = *profit[v];

        if(cur.size() == 0 && val[v] < 0) {
            continue;
        } 
        if(cur.size() == 0) {
            cur.insert({req, val[v]});
            continue;
        }
        
        ll prof = val[v];
        for(auto x : g[v]) {
            if(x == biggest) continue;
            auto& temp = *profit[x];
            for(auto&[r, p] : temp) {
                if(p <= 0) continue;
                cur.insert({r, p});
            }
            delete(profit[x]);
        }
        while(prof <= 0 && cur.size() > 0) {
            auto[r, p] = *cur.begin();
            cur.erase(cur.find({r, p}));
            if(prof <= 0) {
                req = max(req, r - prof);
                prof += p;
            }
        }
        if(prof > 0) {
            while(cur.size() > 0 && (*cur.begin()).first <= req) {
                prof += (*cur.begin()).second;
                cur.erase(cur.begin());
            }
            cur.insert({req, prof});
        }
    }

    auto& fin = *profit[0];
    ll ans = s;
    for(auto[r, p] : fin) {
        if(ans < r) break;
        ans += p;
    }
    cout << ans - s << '\n';
    return 0;
}
/*
6 6
-5 0
-1 1
10 2
-1 1
3 4
5 1


3 5
-5 0
4 1
4 1

ans: 3

5 2
-3 0
-5 1
7 2
9 0
3 2
ans: 11

5 4
-3 0
-2 1
100 2
-4 0
5 4

ans: 6

7 1
-3 0
-2 1
0 2
1 3
2 1
4 4
3 0

ans: 5


9 3
-3 0
-1 1
5 2
-2 1
4 4
-8 1
10 6
1 0
-2 8

*/

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