제출 #1309767

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

Main

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

int n;
long long base, res;
// Sửa: Dùng vector để giữ thứ tự, thêm mảng merged
vector<int> chosen[maxn];
bool merged[maxn]; 

pair<long long, int> a[maxn];
vector<int> adj[maxn];
priority_queue<pair<long long, int>> posi, nega;

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

inline void DFS(int u){
    if (a[u].first >= 0){
        dp[u].cost = 0;
        dp[u].prof = a[u].first;
        // Node dương không cần gộp con để "cứu" nó, chỉ cần duyệt tiếp
        for (int v : adj[u])
            DFS(v);
        return;
    }
    else{
        dp[u].cost = dp[u].prof = a[u].first;
        
        vector<int> vec;
        for (int v : adj[u]){
            DFS(v);
            // Chỉ xem xét gộp những node con không bị loại bỏ (-inf)
            if (dp[v].cost != -inf)
                vec.push_back(v);
        }

        // Sắp xếp con nào "rẻ" nhất (ít âm nhất) chạy trước
        sort(vec.begin(), vec.end(), [](int i, int j){
            return dp[i].cost > dp[j].cost;
        });

        for (int v : vec){
            // Logic tính cost: Min của cost hiện tại VÀ (profit hiện tại + cost của con tiếp theo)
            dp[u].cost = min(dp[u].cost, dp[u].prof + dp[v].cost);
            dp[u].prof += dp[v].prof;
            
            // Lưu lại con được chọn vào vector theo đúng thứ tự
            chosen[u].push_back(v);
            merged[v] = true; // Đánh dấu đã gộp

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

    // Nếu gộp xong vẫn lỗ vốn (net negative) thì coi như nhánh này bỏ đi (vì mục tiêu là max profit)
    if (dp[u].prof <= 0){
        dp[u].cost = dp[u].prof = -inf;
        chosen[u].clear(); // Xóa chosen để tránh update nhầm
    }
}

// Hàm update sửa đổi: Chạy u, sau đó chạy các con trong chosen, và mở khóa các con khác
inline void execute_job(int u){
    res += a[u].first;
    
    // 1. Mở khóa những con KHÔNG được gộp (nằm ngoài block)
    for (int v : adj[u]){
        if (!merged[v]){
            if (a[v].first >= 0) 
                posi.push({a[v].first, v});
            else if (dp[v].cost != -inf) 
                nega.push({dp[v].cost, v});
        }
    }

    // 2. Chạy tiếp các con ĐÃ gộp theo đúng thứ tự đã tính trong DFS
    for (int v : chosen[u]){
        execute_job(v);
    }
}

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);
    }

    // DFS từ các node gốc (p=0)
    for (int i = 1; i <= n; ++i) if (a[i].second == 0){
        DFS(i);
        // Chỉ push vào hàng đợi những node chưa bị gộp (đây là các root block)
        if (!merged[i]) {
            if (a[i].first >= 0) 
                posi.push({a[i].first, i});
            else if (dp[i].cost != -inf) 
                nega.push({dp[i].cost, i});
        }
    }

    while(!posi.empty() || !nega.empty()){
        if (!posi.empty()){
            auto [cost, u] = posi.top();
            posi.pop();
            // Node dương luôn an toàn để lấy
            execute_job(u);
        }
        else if (!nega.empty()){
            auto [cost, u] = nega.top();
            nega.pop();
            
            // Kiểm tra xem có đủ tiền để chịu được mức sụt giảm (cost) thấp nhất của block này không
            // base + res là số tiền hiện tại. cost là số âm.
            if (base + res + cost < 0)
                break;
                
            execute_job(u);
        }
    }

    cout << res;
    return 0;
}

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