제출 #1132719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132719		crafticat	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	241 ms	40572 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (ll i = 0; i < n;i++)
#define FOR(i,j, n) for (ll i = j; i < n;i++)

using ll = long long;
template<typename T>
using V = vector<T>;
using vi = V<ll>;
using pi = pair<ll,ll>;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr ll INF = 1e18;

ll solve(const vi &d1,const vi &d2, ll n, ll k) {
    V<pair<pi, ll>> updates; // Y, X, type

    FOR(i, 1, n + 1) {
        updates.emplace_back(make_pair(d1[i], d2[i]), 1ll);
        updates.emplace_back(make_pair(k - d2[i] + 1, k - d1[i] + 1),0);
    }

    std::sort(updates.begin(), updates.end());
    std::reverse(updates.begin(), updates.end());
    Tree<pi> items;
    ll R = 0;
    ll ans = 0;

    for (auto [p, t] : updates) {
        if (t == 1) {
            items.insert({p.second,R++ });
        }
        if (t == 0) {
            ans += items.size() - items.order_of_key({p.second, -INF}) - 1; // Self
        }
    }

    ans /= 2;
    return n * (n - 1) / 2 - (ans);
}

vi dikstra(ll x, V<V<pi>> &g) {
    vi results(g.size(), INF);

    priority_queue<pi, V<pi>, greater<>> pq;

    pq.emplace(0, x);
    while (!pq.empty()) {
        auto [d, node] = pq.top(); pq.pop();
        if (results[node] != INF) continue;
        results[node] = d;

        for (auto [y, c] : g[node]) {
            if (results[y] != INF) continue;
            pq.emplace(c + d, y);
        }
    }

    return results;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll n, m; cin >> n >> m;
    ll a, b, t, k; cin >> a >> b >> t >> k;
    ll k2 = k;
    k -= t;
    V<V<pi>> g(n + 1);
    F0R(i, m) {
        ll x, y, z; cin >> x >> y >> z;
        g[x].emplace_back(y,z);
        g[y].emplace_back(x,z);
    }

    vi d1 = dikstra(a, g);
    vi d2 = dikstra(b, g);

    if (d1[b] <= k2) {
        cout << (n * (n - 1)) / 2;
        return 0;
    }

    cout << solve(d1, d2, n, k);

    return 0;
}

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