Submission #1178702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178702		gyg	Jobs (BOI24_jobs)	C++20	14 / 100	390 ms	93684 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;

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

void mrg(set<pii>& x, set<pii>& y) { // y into x
    if (x.size() < y.size()) x.swap(y);
    for (pii z : y) x.insert(z);
}

arr<set<pii>, N> dp;
void dfs(int u = 0) {
    for (int v : ch[u]) {
        dfs(v);
        mrg(dp[u], dp[v]);
    }

    pii x = {max(-vl[u], 0ll), vl[u]};
    while (dp[u].size() && (x.sec <= 0 || x > *dp[u].begin())) {
        pii y = *dp[u].begin(); dp[u].erase(dp[u].begin());
        x = {max(x.fir, y.fir - x.sec), x.sec + y.sec};
    }
    if (x.sec <= 0) return;
    dp[u].insert(x);
}

void cmp() {
    int t = s;
    for (pii x : dp[0]) {
        if (t < x.fir) continue;
        t += x.sec;
    }
    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 (pii x : dp[0]) {
    //     cout << x.fir << " " << x.sec << '\n';
    // }

    cmp();
}

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