제출 #1093140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1093140		eysbutno	다리 (APIO19_bridges)	C++17	14 / 100	2284 ms	8356 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

struct DisjointSet {
    vector<int> par, sub;
    stack<int> stk;
    DisjointSet(int n) : par(n), sub(n) {
        iota(all(par), 0);
        fill(all(sub), 1);
    }
    int find(int a) {
        return par[a] == a ? a : find(par[a]);
    }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) { return; }
        if (sub[a] < sub[b]) { swap(a, b); }
        sub[a] += sub[b];
        par[b] = a;
        stk.push(b);
    }
    void rollback(int x) {
        while (sz(stk) > x) {
            int cur = stk.top(); stk.pop();
            sub[par[cur]] -= sub[cur];
            par[cur] = cur;
        }
    }
    inline int edges() { return sz(stk); }
    inline int size(int a) { return sub[find(a)]; }
};
constexpr int B = 512;
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m), d(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> d[i];
        --u[i], --v[i];
    }
    int q; cin >> q;
    vector<int> t(q), a(q), b(q);
    for (int i = 0; i < q; i++) {
        cin >> t[i] >> a[i] >> b[i], --a[i];
    }
    vector<int> res(q, -1);
    for (int i = 0; i < q; i += B) {
        int j = min(i + B, q);
        vector<bool> upd(m);
        vector<int> calc, diff;
        for (int x = i; x < j; x++) {
            if (t[x] == 1) {
                upd[a[x]] = true;
                diff.push_back(x);
            } else {
                calc.push_back(x);
            }
        }
        vector<int> fixed;
        for (int x = 0; x < m; x++) {
            if (!upd[x]) { fixed.push_back(x); }
        }
        sort(all(fixed), [&](int x, int y) { return d[x] > d[y]; });
        sort(all(calc), [&](int x, int y) { return b[x] > b[y]; });
        DisjointSet dsu(n);
        int ptr = 0;
        for (int x : calc) {
            while (ptr < sz(fixed) && d[fixed[ptr]] >= b[x]) {
                dsu.unite(u[fixed[ptr]], v[fixed[ptr]]);
                ++ptr;
            }
            int prv = dsu.edges();
            for (int y : diff) {
                if (y > x && d[a[y]] >= b[x]) {
                    dsu.unite(u[a[y]], v[a[y]]);
                }
                if (y < x && b[y] >= b[x]) {
                    dsu.unite(u[a[y]], v[a[y]]);
                }
            }
            res[x] = dsu.size(a[x]);
            dsu.rollback(prv);
        }
        for (int x : diff) {
            d[a[x]] = b[x];
        }
    }
    for (int x : res) {
        if (x == -1) { continue; }
        cout << x << "\n";
    }
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
*/

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