Submission #1004512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004512		victor_gao	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	145 ms	29436 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define x first
#define y second
#define N 200015
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, s, t, l, k, ans = 0;
vector<pii> G[N];
vector<int> dijkstra(int st){
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    vector<int> dis;
    dis.resize(n + 1, 1e18);
    dis[st] = 0; 
    pq.push({dis[st], st});
    while (!pq.empty()){
        pii now = pq.top(); pq.pop();
        if (now.x != dis[now.y])
            continue;
        for (auto [i, c] : G[now.y]){
            if (dis[i] > now.x + c){
                dis[i] = now.x + c;
                pq.push({dis[i], i});
            }
        }
    }
    return dis;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    vector<int> dis1 = dijkstra(s);
    vector<int> dis2 = dijkstra(t);
    vector<int> dis3 = dis2;
    if (dis1[t] <= k){
        cout << n * (n - 1) / 2 << '\n';
        return 0;
    }
    sort(dis2.begin(), dis2.end());
    for (int i = 1; i <= n; i++){
        int need = k - dis1[i] - l;
        int can = upper_bound(dis2.begin(), dis2.end(), need) - dis2.begin();
        ans += can;
        if (dis3[i] <= need)
            ans--;
    }
    cout << ans << '\n';
}

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