Submission #1165155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165155		quannnguyen2009	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	149 ms	23724 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=2e5+5, mod = 1e9+7, inf = 1e18;

int n, m;
int s, t, l, k;
vector<ii> adj[N];
int d1[N], d2[N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> s >> t >> l >> k;
    for (int i=1; i<=m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (int i=1; i<=n; i++) d1[i] = d2[i] = inf;
    priority_queue<ii, vector<ii>, greater<ii>> pq;   
    d1[s] = 0;
    pq.push({0, s});
    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d!=d1[u]) continue;
        for (auto [v, w]: adj[u]) {
            if(d1[v]>d1[u]+w) {
                d1[v] = d1[u]+w;
                pq.push({d1[v], v});
            }
        }
    }
    if(d1[t]<=k) {
        cout << n*(n-1)/2;
        return 0;
    }
    sort(d1+1, d1+n+1, greater<int>());   
    int ans = 0;
    d2[t] = 0;   
    pq.push({0, t});
    int idx = 1;
    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d!=d2[u]) continue;
        while(idx<=n && d1[idx]+l+d>k) idx++;
        ans += n-idx+1;
        for (auto [v, w]: adj[u]) {
            if(d2[v]>d2[u]+w) {
                d2[v] = d2[u]+w;
                pq.push({d2[v], v});
            }
        }
    }
    cout << ans;
}

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