제출 #1168419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168419		thinknoexit	Bridges (APIO19_bridges)	C++20	59 / 100	3091 ms	7244 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int U[N], V[N], W[N], W2[N];
bool ch[N];
int Q1[N], Q2[N], Q3[N];
int p[N], sz[N], ans[N]; // Union by size
int fr1(int i) {
    if (p[i] == i) return i;
    return p[i] = fr1(p[i]);
}
int fr2(int i) {
    if (p[i] == i) return i;
    return fr2(p[i]);
}
struct Edge {
    int u, v, w, t;
    bool operator < (const Edge& o) const {
        if (w != o.w) return w > o.w;
        return t < o.t;
    }
};
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        cin >> U[i] >> V[i] >> W[i];
    }
    int q;
    cin >> q;
    for (int i = 1;i <= q;i++) {
        cin >> Q1[i] >> Q2[i] >> Q3[i];
    }
    // split into sqrt(q) block
    int sq = sqrt(q);
    for (int i = 1, j = sq;i <= q;i += sq, j = min(q, j + sq)) {
        //cout << "Block " << i << ":\n-----------\n";
        for (int i = 1;i <= n;i++) {
            p[i] = i, sz[i] = 1;
        }
        memset(ch, 0, sizeof ch);
        vector<Edge> Q;
        vector<int> upd_e;
        for (int l = i;l <= j;l++) {
            if (Q1[l] == 1) {
                ch[Q2[l]] = 1;
                upd_e.push_back(l);
            }
            else Q.push_back({ Q2[l], l, Q3[l], 1 });
        }
        for (int j = 1;j <= m;j++) {
            if (!ch[j]) Q.push_back({ U[j], V[j], W[j], 0 });
        }
        sort(Q.begin(), Q.end());
        for (auto& x : Q) {
            //cout << x.u << ' ' << x.v << ' ' << x.w << ' ' << x.t << '\n';
            if (x.t == 0) { // Update without rollback
                int pu = fr1(x.u), pv = fr1(x.v);
                if (pu != pv) {
                    if (sz[pu] < sz[pv]) swap(pu, pv);
                    // pv is under pu
                    p[pv] = pu;
                    sz[pu] += sz[pv];
                }
                continue;
            }
            int t = x.v, w = x.w;
            for (auto& x : upd_e) W2[Q2[x]] = W[Q2[x]];
            for (auto& x : upd_e) {
                if (x <= t) W2[Q2[x]] = Q3[x];
                else break;
            }
            stack<pair<int, int>> rollback; // (pu, pv), p[pv] = pu
            for (auto& x : upd_e) {
                if (W2[Q2[x]] < w) continue;
                int pu = fr2(U[Q2[x]]), pv = fr2(V[Q2[x]]);
                if (pu == pv) continue;
                if (sz[pu] < sz[pv]) swap(pu, pv);
                // pv is under pu
                p[pv] = pu;
                sz[pu] += sz[pv];
                rollback.push({ pu, pv });
            }
            ans[t] = sz[fr2(x.u)];
            while (!rollback.empty()) {
                auto x = rollback.top();
                rollback.pop();
                sz[x.first] -= sz[x.second];
                p[x.second] = x.second;
            }
        }
        for (int l = i;l <= j;l++) { // Post-Process
            if (Q1[l] == 1) {
                W[Q2[l]] = Q3[l];
            }
        }
    }
    for (int i = 1;i <= q;i++) {
        if (Q1[i] == 2) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

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