제출 #1364279

#제출 시각아이디문제언어결과실행 시간메모리
1364279kawhiet다리 (APIO19_bridges)C++20
14 / 100
47 ms4084 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

constexpr int N = 50000;

struct DSU {
    int n;
    vector<int> p, s;

    DSU(int _n) {
        n = _n;
        p.assign(n, -1);
        s.assign(n, 1);
    }

    int root(int x) {
        return (p[x] == -1 ? x : p[x] = root(p[x]));
    }

    void link(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            p[y] = x;
            s[x] += s[y];
        }
    }

    int get(int x) {
        x = root(x);
        return s[x];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> e;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        e.push_back({u, v, w});
    }
    int q;
    cin >> q;
    vector<array<int, 3>> qs(q);
    for (int i = 0; i < q; i++) {
        int t, s, w;
        cin >> t >> s >> w;
        s--;
        qs[i] = {s, w, i};
    }
    sort(qs.begin(), qs.end(), [&](auto x, auto y) {
        return x[1] > y[1];
    });
    sort(e.begin(), e.end(), [&](auto x, auto y) {
        return x[2] > y[2];
    });
    vector<int> ans(q);
    DSU dsu(n);
    int pos = 0;
    for (auto [s, w, i] : qs) {
        while (pos < m && e[pos][2] >= w) {
            auto [u, v, d] = e[pos];
            dsu.link(u, v);
            pos++;
        }
        ans[i] = dsu.get(s);
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…