Submission #1240213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240213		rythm_of_knight	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	130 ms	25108 KiB

Main

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ar array
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
const ll inf = 1e18;
vector <ar <int, 2>> g[N];

void go(int s, vector <ll> &dis) {
    dis[s] = 0;
    priority_queue <ar <ll, 2>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto now = pq.top(); pq.pop();
        int x = now[1];
        ll ds = -now[0];
        if (dis[x] < ds) continue;
        for (auto u : g[x]) {
            if (dis[u[0]] > dis[x] + u[1]) {
                dis[u[0]] = dis[x] + u[1];
                pq.push({-dis[u[0]], u[0]});
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, m, s, t, l, k;
    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 <ll> ds(n + 1, inf), dt(n + 1, inf), sv(n + 1);
    go(s, ds);
    go(t, dt);
    if (ds[t] <= k)
        return cout << n * (n - 1) / 2 << '\n', 0;
    for (int i = 1; i <= n; i++)
        sv[i] = dt[i];
    dt[0] = 0;
    sort(all(dt));
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        ll cur = ds[i] + l;
        cur = k - cur;
        if (cur < 0)
            continue;
        int j = upper_bound(all(dt), cur) - dt.begin() - 1;
        res += j - (sv[i] <= cur);
    }
    cout << res << '\n';
}

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