Submission #1237476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237476		t_holl	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	1068 ms	132476 KiB

Main

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

const int INF = 5e17;

struct Road {
    int a, b, cost;

    int next (int u) {
        return u == a ? b : a;
    }
};

vector<Road> road_list;
vector<vector<int>> roads;

int N;

struct point {
    int x, y;
    int sum_weight;
    int res_weight;

    bool operator< (const point &other) {
        if (x != other.x) return x > other.x;
        if (y != other.y) return y > other.y;

        return sum_weight > other.sum_weight;
    }
};

map<int, int> ccp (vector<int> vals) {
    set<int> u;
    for (int i : vals) u.insert(i);

    map<int, int> res;
    int off = 0;
    for (int i : u)
        res[i] = off ++;
    
    return res;
}

struct SegTree {
    vector<int> tree;
    int size, start, height;
    SegTree (int _size) {
        size = _size;
        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1);
    }
    void update (int i, int d) {
        i += start;
        while (i != 0) {
            tree[i] += d;
            i >>= 1;
        }
    }
    int query (int l) {
        int r = size - 1;
        l += start;
        r += start;

        int res = 0;
        while (l < r) {
            if ((l & 1) == 1) res += tree[l];
            if ((r & 1) == 0) res += tree[r];

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }
        if (l == r) res += tree[l];
        return res;
    }
};

int sum_qp (vector<point> points, int delta) {
    vector<int> px, py;
    for (auto p : points) { px.push_back(p.x); py.push_back(p.y); }
    map<int, int> mx = ccp(px);
    map<int, int> my = ccp(py);
    for (auto &p : points) {
        p.x = mx[p.x];
        p.y = my[p.y];
    }

    sort(points.begin(), points.end());

    SegTree tree(my.size());
    int res = 0;
    for (auto p : points) {
        res += p.res_weight * tree.query(p.y);
        tree.update(p.y, p.sum_weight);
    }

    return (res - delta) >> 1;
}

vector<int> dijkstra (int start) {
    priority_queue<pair<int, int>> queue;
    vector<int> distances(N, INF);

    distances[start] = 0;
    queue.push({ 0, start });

    while (queue.size() != 0) {
        pair<int, int> u = queue.top();
        queue.pop();

        int curr = u.second;
        int dist = - u.first;
        if (distances[curr] != dist) continue ;

        for (int r_id : roads[curr]) {
            int next = road_list[r_id].next(curr);
            int cost = dist + road_list[r_id].cost;

            if (distances[next] <= cost) continue ;

            distances[next] = cost;
            queue.push({ - cost, next });
        }
    }

    return distances;
}

void solve () {
    cin >> N;
    int M; cin >> M;

    int s, t, l, k;
    cin >> s >> t >> l >> k;
    s --; t --;

    roads.resize(N);
    for (int i = 0; i < M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a --,
        b --;

        road_list.push_back({ a, b, c });

        roads[a].push_back(i);
        roads[b].push_back(i);
    }

    int count = (N * (N - 1)) >> 1;

    vector<int> d_s = dijkstra(s);
    vector<int> d_t = dijkstra(t);

    if (d_s[t] <= k) {
        cout << count << "\n";
        return ;
    }

    vector<point> points;
    int delta = 0;
    for (int i = 0; i < N; i ++) {
        points.push_back({ d_s[i], d_t[i], 1, 0 });
        points.push_back({ k - l - d_t[i] + 1, k - l  - d_s[i] + 1, 0, 1 });

        if (k - l - d_s[i] + 1 <= d_t[i] && k - l - d_t[i] + 1 <= d_s[i]) {
            delta ++;
        }
    }

    count -= sum_qp(points, delta);
    cout << count << "\n";
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

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