제출 #1229395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229395		trimkus	Bridges (APIO19_bridges)	C++20	14 / 100	126 ms	5048 KiB

bridges

#include <bits/stdc++.h>

using namespace std;


struct DSU {
    vector<int> e;
    DSU(int n) {
        e = vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    int size(int x) {
        return -e[get(x)];
    }
    void unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) return;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<array<int, 4>> events;
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        events.push_back({-c, -1, a, b});
    }
    int q;
    cin >> q;
    vector<int> res(q);
    for (int i = 0; i < q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        events.push_back({-c, i, b, -1});
    }
    sort(begin(events), end(events));
    DSU dsu(N + 1);
    for (auto& [w, i, a, b] : events) {
        // cout << w << " " << i << " " << a << " " << b << "\n";
        if (i == -1) {
            dsu.unite(a, b);
        } else {
            // cout << dsu.size(a) << "\n";
            res[i] = dsu.size(a);
        }
    }
    for (auto& u : res) {
        cout << u << "\n";
    }
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27