Submission #1309765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309765		harryleee	Jobs (BOI24_jobs)	C++20	0 / 100	176 ms	59000 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5;
const long long inf = 2e18;

int n;
long long base, res;
set<int> chosen[maxn + 1];
pair<long long, int> a[maxn + 1];
vector<int> adj[maxn + 1];
priority_queue<pair<long long, int>> posi, nega;

struct sct{
    long long cost, prof;
    inline sct(){
        cost = prof = 0;
    }
} dp[maxn + 1];

inline void DFS(int u){
    if (a[u].first >= 0){
        dp[u].cost = 0;
        dp[u].prof = a[u].first;

        for (int v : adj[u])
            DFS(v);
        return;
    }
    else{
        dp[u].cost = dp[u].prof = a[u].first;
        for (int v : adj[u])
            DFS(v);

        vector<int> vec;
        for (int v : adj[u]) if (dp[v].cost != -inf)
            vec.push_back(v);

        sort(vec.begin(), vec.end(), [](int i, int j){
            return dp[i].cost > dp[j].cost;
        });

        for (int v : vec){
            dp[u].cost = min(dp[u].cost, dp[u].prof + dp[v].cost);
            dp[u].prof += dp[v].prof;
            chosen[u].insert(v);

            if (dp[u].prof > 0) break;
        }
    }

    if (dp[u].prof <= 0){
        dp[u].cost = dp[u].prof = -inf;
        chosen[u].clear();
    }
    return;
}

inline void update(int u, bool path){
    if (!path){
        if (a[u].first >= 0)
            posi.push({a[u].first, u});
        else if (dp[u].cost != -inf){
            nega.push({dp[u].cost, u});
        }
    }
    else{
        res += a[u].first;
        for (int v : adj[u])
            update(v, (chosen[u].find(v) != chosen[u].end()));
    }

    return;
}

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

    cin >> n >> base;
    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);
    }

    for (int i = 1; i <= n; ++i) if (a[i].second == 0){
        DFS(i);
        if (a[i].first >= 0) 
            posi.push({a[i].first, i});
        else if (dp[i].cost != -inf) 
            nega.push({dp[i].cost, i});
    }

    // for (int i = 1; i <= n; ++i){
    //     cout << dp[i].cost << ' ' << dp[i].prof << '\n';
    // }

    while(!posi.empty() || !nega.empty()){
        if (!posi.empty()){
            auto [cost, u] = posi.top();
            posi.pop();
            res += cost;

            for (int v : adj[u]){
                if (a[v].first >= 0)
                    posi.push({a[v].first, v});
                else if (dp[v].cost != -inf){
                    nega.push({dp[v].cost, v});
                }
            }
        }
        else if (!nega.empty()){
            auto [cost, u] = nega.top();
            nega.pop();
            if (base + res + cost < 0)
                break;
                
            update(u, true);
        }
    }

    cout << res;
    return 0;
}

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