제출 #1253863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253863		skibidihehe	Jobs (BOI24_jobs)	C++20	0 / 100	108 ms	20928 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define ld long double

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll s;
    cin >> N >> s;
    vector<ll> x(N+1);
    vector<int> p(N+1), indeg(N+1, 0);
    vector<vector<int>> g(N+1);
    for(int i = 1; i <= N; i++){
        cin >> x[i] >> p[i];
        if(p[i] != 0){
            g[p[i]].pb(i);
            indeg[i]++;
        }
    }

    ll initial = s;
    ll ans = 0;

    queue<int> pos;                             // việc có lợi (x[i]>=0)
    priority_queue<pair<ll,int>> neg;           // việc lỗ (x[i]<0), ưu tiên lỗ ít trước

    // Khởi tạo
    for(int i = 1; i <= N; i++){
        if(indeg[i] == 0){
            if(x[i] >= 0)  pos.push(i);
            else           neg.push({x[i], i});
        }
    }

    // Xử lý tất cả việc có lợi trước
    while(!pos.empty()){
        int u = pos.front(); pos.pop();
        s   += x[u];
        ans += x[u];
        for(int v : g[u]){
            if(--indeg[v] == 0){
                if(x[v] >= 0)  pos.push(v);
                else           neg.push({x[v], v});
            }
        }
    }

    // Sau khi không còn việc >=0, cố gắng “mở khóa” các việc <0 nếu vẫn đủ tiền
    bool progress = true;
    while(progress){
        progress = false;
        while(!neg.empty()){
            auto [cx, u] = neg.top();
            if(s + cx >= 0){
                // đủ tiền làm
                neg.pop();
                s   += x[u];
                ans += x[u];
                for(int v : g[u]){
                    if(--indeg[v] == 0){
                        if(x[v] >= 0)  pos.push(v);
                        else           neg.push({x[v], v});
                    }
                }
                // sau khi mở thêm, lại chuyển về xử lý các việc >=0
                while(!pos.empty()){
                    int t = pos.front(); pos.pop();
                    s   += x[t];
                    ans += x[t];
                    for(int w : g[t]){
                        if(--indeg[w] == 0){
                            if(x[w] >= 0)  pos.push(w);
                            else           neg.push({x[w], w});
                        }
                    }
                }
                progress = true;
            } else {
                break;
            }
        }
    }

    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