Submission #1356793

#TimeUsernameProblemLanguageResultExecution timeMemory
1356793guardianecConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n;
vector<vector<pair<ll,ll>>> adj;
vector<ll> dijkstra(ll s) {
    vector<ll> dist(n, 1e18);
    dist[s] = 0;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    pq.push({0, s});
    while(!pq.empty()) {
        auto [d,u] = pq.top();
        pq.pop();
        
        if (d>dist[u]) continue;
        for (auto [v,w] : adj[u]) {
            if (dist[v]>dist[u]+w) {
                dist[v] = dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    return dist;
}

vector<ll> T;

void update(ll idx, ll val) {
    for (; idx<=n; idx+=idx & -idx) {
        T[idx]+=val;
    }
}

ll sum(ll idx) {
    ll res = 0;
    for (; idx>0; idx-=idx & -idx) {
        res+=T[idx];
    }
    return res;
}

bool comp(pair<ll,ll> a, pair<ll,ll>b) {
    return a.first-a.second<=b.first-b.second;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll m,s,t,l,k;
    cin >> n >> m >> s >> t >> l >> k;
    s--; t--;
    adj.resize(n);
    T.resize(n+1);
    for (int i=0; i<m; i++) {
        ll a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    
    vector<ll> dists = dijkstra(s);
    vector<ll> distt = dijkstra(t);
    
    if (dists[t]<=k) {
        cout << (n*(n-1))/2;
        return 0;
    }
    
    ll res = 0;
    vector<pair<ll,ll>> v(n);
    for (int i=0; i<n; i++) {
        v[i] = {dists[i], distt[i]};
    }
    
    sort(v.begin(), v.end(), comp);
    map<ll,ll> mp;
    vector<ll> b;
    for (int i=0; i<n; i++) {
        b.push_back(v[i].first);
        b.push_back(k-l-v[i].second);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    
    ll j = 0;
    for (int i=0; i<b.size(); i++) {
        if (i==0 || b[i]>b[i-1]) {
            mp[b[i]] = j++;
        }
    }
    
    for (int i=0; i<n; i++) {
        ll k1 = sum(mp[k-l-v[i].second]);
        res+=k1;
        update(mp[v[i].first], 1);
    }
    
    cout << res;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...