Submission #1309182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309182		IUA_Hasin	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	206 ms	28316 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll INF = 2e18;

// Dijkstra to find shortest paths from a source
void dijkstra(int n, int start, const vector<vector<pair<int, int>>>& adj, vector<ll>& dist) {
    dist.assign(n + 1, INF);
    dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        ll d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// Fenwick Tree for 2D range counting
struct FenwickTree {
    int size;
    vector<int> tree;
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    void add(int i, int val) {
        for (; i <= size; i += i & -i) tree[i] += val;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

struct Point { ll x, y; };
struct Query { ll x_lim, y_lim, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    int S, T;
    ll L, K;
    cin >> S >> T >> L >> K;

    vector<vector<pair<int, int>>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    vector<ll> X(N + 1), Y(N + 1);
    dijkstra(N, S, adj, X);
    dijkstra(N, T, adj, Y);

    // If already happy, all pairs work
    if (X[T] <= K) {
        cout << (ll)N * (N - 1) / 2 << endl;
        return 0;
    }

    ll W = K - L;
    if (W < 0) {
        cout << 0 << endl;
        return 0;
    }

    ll C = 0;
    vector<ll> Y_vals;
    for (int i = 1; i <= N; ++i) {
        if (X[i] + Y[i] <= W) C++;
        Y_vals.push_back(Y[i]);
    }
    sort(Y_vals.begin(), Y_vals.end());

    // Calculate |O|: ordered pairs (u, v) with u != v and X_u + Y_v <= W
    ll ordered_O = 0;
    for (int i = 1; i <= N; ++i) {
        ll limit = W - X[i];
        ordered_O += upper_bound(Y_vals.begin(), Y_vals.end(), limit) - Y_vals.begin();
    }
    ordered_O -= C;

    // Calculate |B|: pairs {u, v} satisfying both conditions using 2D range count
    vector<Point> points(N);
    vector<Query> queries(N);
    for (int i = 0; i < N; ++i) {
        points[i] = {X[i + 1], Y[i + 1]};
        queries[i] = {W - Y[i + 1], W - X[i + 1], i + 1};
    }

    sort(points.begin(), points.end(), [](Point a, Point b) { return a.x < b.x; });
    sort(queries.begin(), queries.end(), [](Query a, Query b) { return a.x_lim < b.x_lim; });

    vector<ll> coords = Y_vals;
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    auto get_idx = [&](ll val) {
        return upper_bound(coords.begin(), coords.end(), val) - coords.begin();
    };

    FenwickTree ft(coords.size());
    ll total_T = 0;
    int pt_idx = 0;
    for (int i = 0; i < N; ++i) {
        while (pt_idx < N && points[pt_idx].x <= queries[i].x_lim) {
            ft.add(get_idx(points[pt_idx].y), 1);
            pt_idx++;
        }
        total_T += ft.query(get_idx(queries[i].y_lim));
    }

    ll unordered_B = (total_T - C) / 2;
    cout << ordered_O - unordered_B << endl;

    return 0;
}

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