제출 #1157214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157214		FilipL	Jobs (BOI24_jobs)	C++20	100 / 100	174 ms	95336 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

#define LOCAL false

const int LIM = 3e5 + 7;
int V;
ll s;

int vals[LIM];
vector<int> tree[LIM];
vector<int> roots;

ll calc(int v) {
    ll tot = vals[v];
    for (int to: tree[v]) tot += max(0LL, calc(to));
    return max(0LL, tot);
}

void pod1() {
    ll ans = 0;
    for (int r: roots) ans += calc(r);
    cout << ans << "\n";
}

pll step[LIM];           // (cost, profit)
vector<int> after[LIM];  // nastepne wierzcholki po kroku

void dfs(int v) {
    for (int to: tree[v]) dfs(to);

    priority_queue<pair<pll, int>, vector<pair<pll, int>>, greater<>> Q;
    for (int to: tree[v]) Q.push({step[to], to});

    ll profit = vals[v];
    ll cost = max(0LL, -profit);
    while (profit < 0 && !Q.empty()) {
        auto [dataa, curv] = Q.top();
        auto [cost2, profit2] = dataa;
        Q.pop();
        if (profit2 < 0) break;
        cost = max(cost, cost2-profit);
        profit += profit2;
        for (int nxt: after[curv]) Q.push({step[nxt], nxt});
    }

    if (profit < 0) step[v] = {LLONG_MAX, -1};
    else {
        step[v] = {cost, profit};
        while (!Q.empty()) {
            auto [dataa, curv] = Q.top();
            Q.pop();
            after[v].push_back(curv);
        }
    }
}

void pod234() {
    for (int r: roots) dfs(r);

    priority_queue<pair<pll, int>, vector<pair<pll, int>>, greater<>> Q;
    for (int r: roots) Q.push({step[r], r});

    ll profit = s;
    while (!Q.empty()) {
        auto [dataa, curv] = Q.top();
        auto [cost2, profit2] = dataa;
        Q.pop();
        if (cost2 > profit) break;
        profit += profit2;
        for (int nxt: after[curv]) Q.push({step[nxt], nxt});
    }
    cout << profit-s << "\n";
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (LOCAL) {
        ignore=freopen("io/in", "r", stdin);
        ignore=freopen("io/out", "w", stdout);
    }

    cin >> V >> s;
    
    int p;
    rep1(v, V) {
        cin >> vals[v] >> p;
        if (p) tree[p].push_back(v);
        else roots.push_back(v);
    }

    if (s == 1000000000000000000LL) {
        pod1();
        return 0;
    }

    pod234();
    return 0;
}

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