Submission #1239078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239078		sunnat	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	384 ms	30188 KiB

Main

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;
#define int long long
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, s, t, l, k;
    cin >> n >> m >> s >> t >> l >> k;
    
    vector<vector<pair<int, int> > > g(n+1);
    for(int i = 0, u, v, w; i < m; ++i){
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    
    const int no_path = 1e18;
    auto djikstra = [&](int from){
        vector<int> dist(n+1, no_path);
        set<pair<int, int>> q;
        dist[from] = 0;
        q.emplace(0, from);
        while(!q.empty()){
            auto [W, v] = *q.begin();
            q.erase(q.begin());
            if(W != dist[v]) continue;
            for(auto [u, w]:g[v])
                if(dist[u] > W + w){
                    q.erase({dist[u], u});
                    dist[u] = W + w;
                    q.emplace(dist[u], u);
                }
        }
        return dist;
    };
    
    auto from_s = djikstra(s);
    if(from_s[t] <= k){
        cout << n * (n - 1) / 2;
        return 0;
    }
    if(l > k){
        cout << 0;
        return 0;
    }
    auto from_t = djikstra(t);
    
    sort(from_s.begin(), from_s.end());
    sort(from_t.begin(), from_t.end());
    int res = 0;
    k -= l;
    for(int i = 0, j = n - 1; i < n; ++ i){
        while(j >= 0 && from_s[i] + from_t[j] > k) -- j;
        res += j + 1;
    }
    cout << res;
    return 0;
}

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