Submission #1257262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257262		kikitop1gg	Jobs (BOI24_jobs)	C++17	0 / 100	140 ms	31680 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);
    }

    vi profit(n + 1, 0);
    vi require(n + 1, -inf);
    for(int i = n; i > 0; i--) {
        ll v = topSort[i];
        profit[v] = val[v];
        if(val[v] < 0) require[v] = -val[v];

        ll prof = profit[v], req = require[v];
        priority_queue<pair<double, pp>> q; // real, req, profit
        for(auto x : g[v]) {
            if(profit[x] < 0) continue;
            double real = inf;
            if(require[x] > -inf) {
                real = double(profit[x]) / double(require[x]);
            }
            q.push({real, {-require[x], profit[x]}});
        }
        while(q.size()) {
            ll curReq = -q.top().second.first, curProf = q.top().second.second;
            q.pop();
            if(curReq < 0) {
                prof += curProf;
            }
            else if(prof < 0) {
                prof += curProf;
                req += curReq, req;
            }
        }

        profit[v] = prof;
        require[v] = req;
    }

    ll ans = s;
    ll cur = s;
    priority_queue<pp> q; // required minimum, vertex
    q.push({0, 0});
    while(q.size()) {
        ll r = -q.top().first, v = q.top().second;
        q.pop();
        if(cur < r) break;
        cur += val[v];
        ans = max(ans, cur);
        
        for(auto x : g[v]) {
            if(profit[x] < 0) continue;
            q.push({-require[x], x});
        }
    }
    ans -= s;
    cout << ans << '\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
*/

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