제출 #1202366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202366		madamadam3	Jobs (BOI24_jobs)	C++20	0 / 100	318 ms	64448 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;

/* current need(u)  = original weight(u) + ( currentGain(u) − originalGain(u) ) */
inline long long current_need(int u, Fenw& fenw) {
    return weight[u] + fenw.query(tin[u]) - value[u];
}

/* multiset of (need, id) with **positive current gain** ----------------- */
multiset< pair<long long,int> > Q;
void push_if_profitable(int v, Fenw& fenw) {
    if (used[v]) return;
    long long gain = fenw.query(tin[v]);
    if (gain > 0) Q.insert({ current_need(v, fenw), v });
};

/* unravel --------------------------------------------------------------- */
void unravel(int u, Fenw& fenw, long long& cash) {   // Q is global
    if (used[u]) return;
    used[u] = 1;

    /* children become independent → maybe profitable now */
    for (int v : adj[u]) {
        dep[v] = 0;
        push_if_profitable(v, fenw);
    }
    adj[u].clear();

    fenw.add(tin[u], tout[u], -profit[u]);   // shift descendants
    cash += profit[u];

    if (dep[u]) unravel(dep[u], fenw, cash);       // climb to parent
    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;
    for (int i = 1; i <= n; ++i)
        if (value[i] > 0) Q.insert({ weight[i], i });

    while (!Q.empty()) {
        auto [need_key, u] = *Q.begin();
        Q.erase(Q.begin());

        if (used[u]) continue;                    // outdated entry

        long long gain_now = fenw.query(tin[u]);
        long long need_now = current_need(u, fenw);

        if (gain_now <= 0) continue;              // no longer profitable
        if (need_now > curs) break;               // nothing else is affordable

        unravel(u, fenw, curs);                   // execute the chain
    }

    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