Submission #1154284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154284		tsengang	Construction Project 2 (JOI24_ho_t2)	C++20	8 / 100	266 ms	30164 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, 1e14), dists(n + 1, 1e14);
    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;
    vector<ll>L,R;
    for(ll i = 1; i <= n; i++){
        L.pb(dists[i]);
        R.pb(distt[i]);
    }
    sort(all(L));
    sort(all(R));
    for(ll i = 1; i <= n; i++){
        ll nm = upper_bound(all(R),k-l-L[i-1])- R.begin();
        ans+=nm;
    }
    cout << ans << '\n';
}

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