제출 #1202353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202353		madamadam3	Jobs (BOI24_jobs)	C++20	0 / 100	288 ms	60408 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, used;
vector<set<int>> adj;
int timer = 0;

void unravel(int u, Fenw &fenw, int &val) {
    if (used[u]++) return;

    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);
    dep[u] = 0;
}

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);
    used.assign(n+1, 0);

    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