Submission #1084829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084829		kilkuwu	Jobs (BOI24_jobs)	C++17	43 / 100	2057 ms	48636 KiB

Main

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

#define nl '\n'

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    int64_t fund;
    std::cin >> N >> fund;

    std::vector<std::vector<int>> adj(N);

    std::vector<int> x(N), p(N);

    std::vector<int> deg(N);
    for (int i = 0; i < N; i++) {
        std::cin >> x[i] >> p[i];
        --p[i];
        if (p[i] != -1) {
            deg[i]++;
            adj[p[i]].emplace_back(i);
        }
    }

    std::vector<int> st(N), en(N), who(N);
    std::vector<int64_t> require(N), path(N);
    int ti = 0;



    std::vector<int64_t> dp(N + 1);
    std::vector<int> take(N);
    std::multiset<std::tuple<int64_t, int64_t, int>> s; // req, i

    auto find_good = [&](int u) -> void {
        require[u] = -x[u];
        path[u] = -x[u];
        for (int i = st[u] + 1; i < en[u]; i++) {
            int v = who[i];
            path[v] = path[p[v]] - x[v];
            require[v] = std::max(require[p[v]], path[v]);
        }

        auto do_dp = [&](int64_t mb) {
            dp[en[u]] = 0;
            for (int i = en[u] - 1; i > st[u]; i--) {
                int v = who[i];
                take[v] = 0;
                dp[i] = dp[en[v]]; // not taking this
                if (require[v] <= mb) { // we can take it
                    if (dp[i] < dp[i + 1] + x[v]) {
                        take[v] = 1;
                        dp[i] = dp[i + 1] + x[v];
                    }
                }
            }
            dp[st[u]] = dp[st[u] + 1] + x[u];
            take[u] = 1;
            return dp[st[u]];
        };

        int64_t lb = std::max(require[u], (int64_t) 0), rb = 1e18;
        int64_t ans = -1;
        while (lb <= rb) {
            int64_t mb = (lb + rb) / 2;

            if (do_dp(mb) >= 0) {
                ans = mb;
                rb = mb - 1;
            } else {
                lb = mb + 1;
            }
        }

        auto prof = do_dp(ans);
        if (ans != -1) s.emplace(ans, prof, u);
    };

    auto resolve = [&](int u) -> void {
        std::vector<int> to_add;
        for (int i = st[u]; i < en[u]; ) {
            int v = who[i];
            if (!take[v]) {
                to_add.emplace_back(v);
                i = en[v];
            } else {
                i++;
            }
        }


        for (int v : to_add) {
            find_good(v);
        }
    };


    for (int i = 0; i < N; i++) {
        if (p[i] == -1) {
            auto dfs = [&](auto self, int u) -> void {
                who[ti] = u;
                st[u] = ti++;
                for (int v : adj[u]) {
                    self(self, v);
                }
                en[u] = ti;
            };
            dfs(dfs, i);
            find_good(i);
        }
    }

    int64_t money = fund;


    while (true) {
        if (s.empty()) {
            break;
        }


        auto [req, prof, u] = *(s.begin());

        s.erase(s.begin());
        if (req > money) {
            break;
        }

        money += prof;

        resolve(u);
    }

    std::cout << money- fund << nl;
}

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