Submission #1212480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212480		VMaksimoski008	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	266 ms	24880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 2e5 + 5;

vector<pll> g[N];
ll D[N][2], n, m, ans = 0;

void shortest_path(int s, int i) {
    for(int j=1; j<=n; j++) D[j][i] = 1e18;
    priority_queue<pll, vector<pll>, greater<> > pq;
    pq.push({ D[s][i] = 0, s });

    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d != D[u][i]) continue;
        for(auto [v, w] : g[u])
            if(D[v][i] > d + w) pq.push({ D[v][i] = d + w, v });
    }
}

signed main() {
    cin >> n >> m;
    ll s, t, L, K; cin >> s >> t >> L >> K;

    while(m--) {
        ll a, b, c; cin >> a >> b >> c;
        g[a].push_back({ b, c });
        g[b].push_back({ a, c });
    }

    shortest_path(s, 0);
    shortest_path(t, 1);

    vector<array<ll, 2> > a;
    for(int i=1; i<=n; i++) a.push_back({ D[i][0], D[i][1] });
    sort(a.begin(), a.end());

    for(int i=0; i<n; i++) {
        int p = upper_bound(a.begin(), a.end(), array<ll, 2>{ K-L-a[i][1], (ll)2e18 }) - a.begin() - 1;
        ans += min(i, p+1);
    }
    cout << (D[t][0] <= K ? (ll)n * (n-1) / 2 : ans) << '\n';
}

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