제출 #1229302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229302		trimkus	다리 (APIO19_bridges)	C++20	0 / 100	124 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, a, -1});
    }
    sort(begin(events), end(events));
    DSU dsu(N + 1);
    for (auto& [w, i, a, b] : events) {
        if (i == -1) {
            dsu.unite(a, b);
        } else {
            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: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27