제출 #1320955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320955		random_name	Jobs (BOI24_jobs)	C++20	0 / 100	186 ms	42060 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,k;cin>>n>>k;

    vector<pair<ll, ll>> A(n);
    for(pair<ll, ll> &i:A) { cin>>i.first>>i.second; i.second--; }

    vector<vector<ll>> childs(n);
    vector<ll> roots;
    for(ll i=0;i<n;i++){
        if(A[i].second == -1){
            roots.push_back(i);
            continue;
        }

        childs[A[i].second].push_back(i);
    }

    ll res=0;
    vector<ll> value(n);
    vector<ll> prereq(n);
    priority_queue<pair<ll, ll>> prereqs;
    stack<ll> dfs;
    for(ll r:roots) dfs.push(r);

    while(!dfs.empty()){
        ll c = dfs.top();
        dfs.pop();

        if(A[c].second == -1){
            value[c] = A[c].first;
            prereq[c] = min(0ll, A[c].first);
        }

        else{
            value[c] = A[c].first + value[A[c].second];
            prereq[c] = min(value[c], prereq[A[c].second]);
        }

        prereqs.push({prereq[c], c});

        for(ll e:childs[c]){
            dfs.push(e);
        }
    }

    priority_queue<pair<ll, ll>> mxvals;
    vector<bool> vis(n, false);
    while(true){
        while(!prereqs.empty() && prereqs.top().first + k >= 0){
            mxvals.push({value[prereqs.top().second], prereqs.top().second});
            prereqs.pop();
        }

        if(mxvals.empty()){
            break;
        }

        ll cur = mxvals.top().second;
        // cout << cur << '\n';
        ll last = cur;
        mxvals.pop();
        ll oldk = k;
        while(cur != -1 && !vis[cur]){
            k += A[cur].first;
            res += A[cur].first;
            A[cur].first = 0;
            vis[cur] = true;
            cur = A[cur].second;
        }

        if(oldk > k){
            A[last].first = k - oldk;
            vis[last] = false;
            res += oldk - k;
            k = oldk;
        }
    }

    cout << res << '\n';
}

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