Submission #1112285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112285		Zero_OP	Construction Project 2 (JOI24_ho_t2)	C++14	53 / 100	2057 ms	26564 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const long long inf = 1e18;

void testcase(){
    int N, M, S, T, L; long long K;
    cin >> N >> M >> S >> T >> L >> K;

    --S, --T;
    vector<vector<pair<int, int>>> adj(N);
    while(M--){
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    auto dijkstra = [&](int s){
        vector<long long> d(N, inf);
        d[s] = 0;

        using node = pair<long long, int>;
        priority_queue<node, vector<node>, greater<node>> pq;
        pq.push({d[s], s});

        while(!pq.empty()){
            long long cur; int u;
            tie(cur, u) = pq.top(); pq.pop();
            for(auto [v, w] : adj[u]){
                if(d[v] > d[u] + w){
                    d[v] = d[u] + w;
                    pq.push({d[v], v});
                }
            }
        }
        return d;
    };

    vector<long long> dS = dijkstra(S), dT = dijkstra(T);

    if(dS[T] <= K){
        cout << 1LL * N * (N - 1) / 2;
        return;
    }

    vector<long long> vS, vT;
    for(int i = 0; i < N; ++i){
        vS.emplace_back(dS[i]);
        vT.emplace_back(dT[i]);
    }

    sort(vS.begin(), vS.end());
    sort(vT.begin(), vT.end());

    long long cnt = 0;
    for(int i = 0; i < N; ++i){
        cnt += upper_bound(vS.begin(), vS.end(), K - L - dT[i]) - vS.begin();
        cnt += upper_bound(vT.begin(), vT.end(), K - L - dS[i]) - vT.begin();
    }

    assert(cnt & 1 ^ 1);
    cout << cnt / 2 << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
//    cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:34:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |             for(auto [v, w] : adj[u]){
      |                      ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'void testcase()':
Main.cpp:66:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   66 |     assert(cnt & 1 ^ 1);
      |            ~~~~^~~

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