Submission #29810834

---

Source Code Expand

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

constexpr ll inf = std::numeric_limits<ll>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<int> A(M), B(M), C(M);
    vector<vector<pair<int, ll>>> list(N);
    ll sum = 0;
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i] >> C[i];
        A[i] -= 1, B[i] -= 1;
        if (A[i] > B[i]) std::swap(A[i], B[i]);
        list[A[i]].emplace_back(B[i], C[i]);
        sum += C[i];
    }
    vector<ll> memo(N);
    std::priority_queue<pair<int, ll>> heap;
    const auto solve = [&](const ll subt) {
        std::fill(memo.begin(), memo.end(), 0);
        heap = decltype(heap)();
        ll cur = 0, turn = 0;
        for (int i = 0; i < N; ++i) {
            cur += memo[i];
            for (const auto& [r, c] : list[i]) {
                cur += c;
                memo[r] -= c;
                heap.emplace(r, c);
            }
            const ll dif = cur - subt;
            ll need = (dif + 1) / 2;
            while (need > 0) {
                if (heap.empty() or heap.top().first <= i) return inf;
                const auto [r, c] = heap.top();
                heap.pop();
                const ll min = std::min(c, need);
                cur -= 2 * min;
                turn += min;
                memo[r] += 2 * min;
                if (min < c) heap.emplace(r, c - min);
                need -= min;
            }
        }
        return subt + turn;
    };
    ll ans = inf;
    for (const int parity : {0, 1}) {
        ll ok = sum + 1, ng = -1;
        while (ok - ng > 1) {
            const ll md = (ok + ng) / 2;
            const ll l = solve(parity + 2 * md);
            if (l == inf) {
                ng = md;
            } else {
                (l <= solve(parity + 2 * md + 2) ? ok : ng) = md;
            }
        }
        ans = std::min(ans, solve(parity + 2 * ok));
    }
    std::cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result