Submission #1178651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178651		gyg	Jobs (BOI24_jobs)	C++20	100 / 100	332 ms	73088 KiB

Main

#include <bits/stdc++.h>   
using namespace std;
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 3e5 + 5, INF = 5e18;

int n, s;
arr<int, N> vl;
arr<vec<int>, N> ch;

arr<int, N> dp;
void dfs(int u = 0) {
    for (int v : ch[u]) dfs(v);
    if (vl[u] >= 0) return;

    set<pii> ord;
    for (int v : ch[u]) ord.insert({dp[v], v});
    
    int st = -vl[u], cr = 0;
    while (ord.size() && st > cr) {
        int v = ord.begin()->sec; ord.erase(ord.begin());
        if (dp[v] == INF) continue;
        if (cr < dp[v]) {
            int df = dp[v] - cr;
            st += df, cr += df;
        }
        cr += vl[v];
        for (int w : ch[v]) ord.insert({dp[w], w});
    }
    dp[u] = (st > cr) ? INF : st;
}

void cmp() {
    set<pii> ord = {{dp[0], 0}};
    int t = s;
    while (ord.size()) {
        int u = ord.begin()->sec; ord.erase(ord.begin());
        if (dp[u] > t) continue;
        t += vl[u];
        for (int v : ch[u]) ord.insert({dp[v], v}); 
    }
    cout << t - s << '\n';
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n >> s;
    for (int u = 1; u <= n; u++) {
        int v; cin >> vl[u] >> v;
        ch[v].push_back(u);
    }

    dfs();
    // for (int u = 1; u <= n; u++)  
    //     cout << u << ": " << dp[u] << '\n';
    cmp();
}

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