Submission #1243920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243920		CrabCNH	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	135 ms	29620 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define pii pair <int, int>

using namespace std;

const int maxN = 2e5 + 5;
const int inf = 1e18 + 7;

struct Edge {
    int u, v, w;
};

int n, m;
int S, T, l, K;
vector <pii> adj[maxN];
vector <Edge> allE;

namespace sub3 {
    int L[maxN][2];

    inline void dijkstra (int st, int t) {
        priority_queue <pii, vector <pii>, greater <pii>> pq;
        for (int i = 1; i <= n; i ++) {
            L[i][t] = inf;
        }
        L[st][t] = 0;
        pq.push ({L[st][t], st});
        while (!pq.empty ()) {
            auto [c, u] = pq.top ();
            pq.pop ();
            if (c > L[u][t]) {
                continue;
            }
            for (auto [v, w] : adj[u]) {
                if (L[v][t] > L[u][t] + w) {
                    L[v][t] = L[u][t] + w;
                    pq.push ({L[v][t], v});
                }
            }
        }
        return;
    }

    inline void sol () {
        dijkstra (S, 0);
        dijkstra (T, 1);
        int minDist = L[T][0];
        if (minDist <= K) {
            cout << n * (n - 1) / 2;
            return;
        }
        int res = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = i + 1; j <= n; j ++) {
                if (min (L[i][0] + L[j][1] + l, L[i][1] + L[j][0] + l) <= K) {
                    res ++;
                }
            }
        }
        cout << res;
        return;
    }
}

namespace sub4 {
    int L[maxN][2];

    inline void dijkstra (int st, int t) {
        priority_queue <pii, vector <pii>, greater <pii>> pq;
        for (int i = 1; i <= n; i ++) {
            L[i][t] = inf;
        }
        L[st][t] = 0;
        pq.push ({L[st][t], st});
        while (!pq.empty ()) {
            auto [c, u] = pq.top ();
            pq.pop ();
            if (c > L[u][t]) {
                continue;
            }
            for (auto [v, w] : adj[u]) {
                if (L[v][t] > L[u][t] + w) {
                    L[v][t] = L[u][t] + w;
                    pq.push ({L[v][t], v});
                }
            }
        }
        return;
    }

    inline void sol () {
        dijkstra (S, 0);
        dijkstra (T, 1);
        int minDist = L[T][0];
        if (minDist <= K) {
            cout << n * (n - 1) / 2;
            return;
        }
        int res = 0;
        vector <int> d0;
        for (int i = 1; i <= n; i ++) {
            d0.push_back (L[i][0]);
        }
        sort (d0.begin (), d0.end ());
        for (int i = 1; i <= n; i ++) {
            int ll = 0, r = n - 1, add = 0;
            while (true) {
                if (ll > r) {
                    break;
                }
                int mid = (ll + r) >> 1;
                if (d0[mid] + L[i][1] + l <= K) {
                    add = mid + 1;
                    ll = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            res += add;
        }
        for (int i = 1; i <= n; i ++) {
            res -= (L[i][1] + L[i][0] + l <= K);
        }
        cout << res;
        return;
    }
}


signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> m;
    cin >> S >> T >> l >> K;
    for (int i = 1; i <= m; i ++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back ({v, c});
        adj[v].push_back ({u, c});
        allE.push_back ({u, v, c});
    }
    sub4 :: sol ();
}

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