Submission #1273928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273928		MisterReaper	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	158 ms	24904 KiB

Main

// File construcproj2.cpp created on 28.09.2025 at 19:27:47
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

int main() {
    std::ios::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<int>> adj(N);
    std::vector<std::array<int, 3>> E(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> E[i][0] >> E[i][1] >> E[i][2];
        --E[i][0], --E[i][1];
        adj[E[i][0]].emplace_back(i);
        adj[E[i][1]].emplace_back(i); 
    }

    auto dijsktra = [&](int st) -> std::vector<i64> {
        min_pq<std::pair<i64, int>> pq;
        std::vector<i64> dis(N, inf);
        pq.emplace(dis[st] = 0, st);
        while (!pq.empty()) {
            auto[d, v] = pq.top();
            pq.pop();
            if (dis[v] != d) {
                continue;
            }
            for (auto i : adj[v]) {
                int u = E[i][0] ^ E[i][1] ^ v;
                if (chmin(dis[u], dis[v] + E[i][2])) {
                    pq.emplace(dis[u], u);
                }
            }
        }
        return dis;
    };

    auto dS = dijsktra(S);
    auto dT = dijsktra(T);

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

    i64 ans = 0;
    std::sort(dS.begin(), dS.end());
    std::sort(dT.begin(), dT.end());

    debug(dS);
    debug(dT);

    int p = N - 1;
    for (int i = 0; i < N; ++i) {
        while (p != -1 && dT[p] + dS[i] + L > K) {
            p--;
        }
        ans += p + 1;
    }

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

    return 0;
}

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