Submission #1148052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148052		MisterReaper	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	215 ms	22696 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

bool chmin(i64& a, i64 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    int S, T, L;
    i64 K;
    std::cin >> S >> T >> L >> K;
    --S, --T;

    std::vector<std::vector<std::pair<int, int>>> adj(N);
    for (int i = 0; i < M; ++i) {
        int A, B, C;
        std::cin >> A >> B >> C;
        --A, --B;
        adj[A].emplace_back(B, C);
        adj[B].emplace_back(A, C);
    }

    std::vector<i64> ds(N, inf), dt(N, inf);
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> pq;
    pq.emplace(ds[S] = 0, S);
    while (!pq.empty()) {
        auto[d, v] = pq.top();
        pq.pop();
        if (ds[v] != d) {
            continue;
        }
        for (auto[u, w] : adj[v]) {
            if (chmin(ds[u], d + w)) {
                pq.emplace(ds[u], u);
            }
        }
    }
    pq.emplace(dt[T] = 0, T);
    while (!pq.empty()) {
        auto[d, v] = pq.top();
        pq.pop();
        if (dt[v] != d) {
            continue;
        }
        for (auto[u, w] : adj[v]) {
            if (chmin(dt[u], d + w)) {
                pq.emplace(dt[u], u);
            }
        }
    }

    debug(ds);
    debug(dt);

    if (ds[T] <= K) {
        i64 all_edges = 1LL * N * (N - 1) / 2;
        std::cout << all_edges << '\n';
        return 0;
    }

    std::vector<i64> vv;
    for (int v = 0; v < N; ++v) {
        if (dt[v] != -1) {
            vv.emplace_back(dt[v]);
        }
    }

    std::sort(vv.begin(), vv.end());

    i64 ans = 0;
    for (int v = 0; v < N; ++v) {
        if (ds[v] == -1) {
            continue;
        }
        i64 new_ds = ds[v] + L;
        if (new_ds <= K) {
            auto it = std::upper_bound(vv.begin(), vv.end(), K - new_ds);
            ans += it - vv.begin();
        }
    }

    std::cout << ans << '\n';

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47