Submission #1154204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154204		tsengang	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	2095 ms	20768 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ertunt return
const int MOD = 998244353;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int main() {
    ll n, m;
    cin >> n >> m;
    ll s, t, l, k;
    cin >> s >> t >> l >> k;
    vector<vector<pair<ll, ll>>> v(n + 1);
    for (ll i = 0; i < m; i++) {
        ll a, b, w;
        cin >> a >> b >> w;
        v[a].pb({b, w});
        v[b].pb({a, w});
    }
    vector<ll> distt(n + 1, 1e18), dists(n + 1, 1e18);
    dists[s] = 0;
    distt[t] = 0;
    set<pair<ll, ll>> pq;
    pq.insert({0, s});
    while (!pq.empty()) {
        auto p = *pq.begin();
        pq.erase(pq.begin());
        for (auto [x, y] : v[p.ss]) {
            if (dists[x] > dists[p.ss] + y) {
                pq.erase({dists[x], x});
                dists[x] = dists[p.ss] + y;
                pq.insert({dists[x], x});
            }
        }
    }
    pq.insert({0, t});
    while (!pq.empty()) {
        auto p = *pq.begin();
        pq.erase(pq.begin());
        for (auto [x, y] : v[p.ss]) {
            if (distt[x] > distt[p.ss] + y) {
                pq.erase({distt[x], x});
                distt[x] = distt[p.ss] + y;
                pq.insert({distt[x], x});
            }
        }
    }
    if (distt[s] <= k) {
        cout << n * (n - 1) / 2;
        ertunt 0;
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        for (ll j = i + 1; j <= n; j++) {
            if (dists[i] + l + distt[j] <= k or distt[i] + l + dists[j] <= k) ans++;
        }
    }
    cout << ans << '\n';
}

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