Submission #1177560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177560		faqinyeager	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	229 ms	24872 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define ub(c, x) distance((c).begin(),lower_bound(c.begin(),c.end(), (x)))
#define N 200015
using namespace std;

const int inf = 1e9;

ll gcd(ll a, ll b){
    if(b == 0) return 1;
    return gcd(b, a % b);
}

ll n, m, s, t, l, k, ans = 0;
vector<pair<ll, ll>> G[N];

vector<ll> dijkstra(ll st){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<ll> 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.first != dis[now.second]) continue;
        for(auto x: G[now.second]){
            ll i = x.first, c = x.second;
            if(dis[i] > now.first + c){
                dis[i] = now.first + c;
                pq.push({dis[i], i});
            }
        }
    }
    return dis;
}

void F(){
    cin >> n >> m >> s >> t >> l >> k;
    rep(i, 0, m){
        ll a, b, c;
        cin >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    vector<ll> dis1 = dijkstra(s);
    vector<ll> dis2 = dijkstra(t);
    vector<ll> dis3 = dis2;

    //for(auto x: dis1) cout << x << ' '; cout << "\n\n";
    //for(auto x: dis2) cout << x << ' '; cout << "\n\n";    

    if(dis1[t] <= k){
        cout << n * (n - 1) / 2 << "\n"; return;
    }
    sort(dis2.begin(), dis2.end());
    rep(i, 1, n + 1){
        ll need = k - dis1[i] - l;
        ll can = upper_bound(dis2.begin(), dis2.end(), need) - dis2.begin();
        ans += can;
        if(dis3[i] <= need) ans--;
    }
    cout << ans << "\n";
}

int main() {

    int tc = 1;
    //cin >> tc;
    while(tc--) F();
}

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