제출 #1257236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257236		kikitop1gg	Jobs (BOI24_jobs)	C++17	0 / 100	165 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];
        for(auto x : g[v]) {
            ll curProf = profit[x] + profit[v];
            ll curReq = max(req, require[x]);
            if(curProf < 0) continue;
            if(curReq < req || (curReq == req && curProf > prof)) {
                req = curReq;
                prof = curProf;
            }
        }
        profit[v] = prof;
        require[v] = req;
    }

    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];
        
        for(auto x : g[v]) {
            if(profit[x] < 0) continue;
            q.push({-require[x], x});
        }
    }
    ll ans = cur - s;
    cout << ans << '\n';
    return 0;
}

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