Submission #1202347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202347		madamadam3	Jobs (BOI24_jobs)	C++20	0 / 100	313 ms	54360 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long int

struct Fenw { // rupq
    int n;
    vector<int> BIT;

    Fenw(int N) {
        n = 2*N;
        BIT.assign(n, 0);
    }

    void add(int idx, int delta) {
        while (idx < n) {
            BIT[idx] += delta;
            idx = idx | (idx + 1);
        }
    }

    void add(int l, int r, int delta) {
        add(l, delta);
        add(r, -delta);
    }

    int query(int r) {
        int res = 0;

        while (r >= 0) {
            res += BIT[r];
            r = (r & (r+1)) - 1;
        }

        return res;
    }
};

vector<int> profit, dep, value, weight, tin, tout;
vector<set<int>> adj;
int timer = 0;

void unravel(int u, Fenw &fenw, int &val) {
    for (auto &el : adj[u]) {
        // if (!used.count(el)) indep.insert(el);
        dep[el] = 0;
    }

    adj[u].clear();

    fenw.add(tin[u], tout[u], -profit[u]);
    val += profit[u];

    if (dep[u] != 0) unravel(dep[u], fenw, val);
}

void dfs(int u, int curv, int min_weight) {
    tin[u] = timer++;

    curv += profit[u];
    min_weight = min({0LL, min_weight, curv});

    weight[u] = min_weight;
    value[u] = curv;

    for (auto &v : adj[u]) {
        dfs(v, curv, min_weight);
    }

    tout[u] = timer;
}

signed main() {
    int n, s; cin >> n >> s;

    adj.assign(n+1, set<int>());
    profit.resize(n+1); dep.resize(n + 1);
    value.assign(n+1, 0); weight.assign(n+1, 0);
    tin.assign(n+1, -1); tout.assign(n + 1, -1);

    for (int i = 1; i <= n; i++) {
        cin >> profit[i] >> dep[i];
        if(dep[i]) adj[dep[i]].insert(i);
    }

    /*
        Idea: each j*b (j slur) forms a rooted tree with its dependencies
        we can assign each node on tree a value (profit we can achieve with it) and a weight (money we need to achieve it)
        we sort every node with positive value by weight and keep on adding, making sure to remove dp of all nodes earlier in the tree
        if ever the min weight of a positive node is > current balance, stop

        use a priority queue by profit for the exploration
    */

    for (int i = 1; i <= n; i++) {
        if (tin[i] != -1) continue;
        dfs(i, 0, 0);
    }

    auto fenw = Fenw(2*n);
    for (int i = 1; i <= n; i++) {
        fenw.add(tin[i], tout[i], profit[i]);
    }

    int curs = s;
    vector<int> indices(n); iota(indices.begin(), indices.end(), 1);
    sort(indices.begin(), indices.end(), [&](int a, int b) {
        return weight[a] > weight[b];
    });

    for (auto &el : indices) {
        if (curs + weight[el] < 0) break;
        if (fenw.query(tin[el]) < 0) continue;
        unravel(el, fenw, curs);
    }

    cout << curs - s;
    return 0;
}

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