제출 #1309737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309737		harryleee	Jobs (BOI24_jobs)	C++20	0 / 100	55 ms	20240 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5;
int n, target[maxn + 1];
long long s, res;
vector<int> adj[maxn + 1];
pair<long long, int> a[maxn + 1];
priority_queue<pair<long long, int>> posi, nega;

inline long long DFS(int u, long long sum){
    sum += a[u].first;
    if (sum > 0) return sum;
    
    long long opt = -2e18;
    for (int v : adj[u]){ 
        long long k = DFS(v, sum);
        if (k > opt){
            k = opt;
            target[u] = v;
        }
    }

    return min(opt, sum);
}

inline void update(int u, bool path){
    if (!path){
        if (a[u].first > 0){
           posi.push({a[u].first, u});
        }    
        else{
            long long k = DFS(u, 0);
            if (k > -2e18) nega.push({k, u});
        }
    }
    else{
        res += a[u].first;
        for (int v : adj[u]){
            update(v, (v == target[u]));
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s;
    res = s;

    for (int i = 1; i <= n; ++i){
        cin >> a[i].first >> a[i].second;
        if (a[i].second != 0)
            adj[a[i].second].push_back(i);
        else{
            if (a[i].first > 0) posi.push({a[i].first, i});
            else nega.push({a[i].first, i});
        }
    }

    while(!posi.empty() && !nega.empty()){
        if (!posi.empty()){
            auto [earn, u] = posi.top();
            posi.pop();

            res += earn;
            for (int v : adj[u]){
                if (a[v].first > 0){
                    posi.push({a[v].first, v});
                }
                else{
                    long long found = DFS(v, 0);
                    if (found != -2e18) nega.push({found, v});
                }
            }
        }
        else{
            auto [cost, u] = nega.top();
            nega.pop();
            if (cost > res) break;

            update(u, 1);
        }
    }

    cout << res - s << '\n';
    return 0;
}

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