Submission #1168441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168441		thinknoexit	Bridges (APIO19_bridges)	C++20	100 / 100	2907 ms	7884 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
inline int fr(int i) {
    while (p[i] != i) i = p[i];
    return 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;
    vector<int> v;
    for (int i = 1;i <= q;i++) {
        cin >> Q1[i] >> Q2[i] >> Q3[i];
        if (Q1[i] == 2) v.push_back(i);
    }
    int M = v.size();
    int sq = min(M, 400);
    if (M == 0) {
        return 0;
    }
    vector<pair<int, int>> S;
    for (int i = 0, j = sq - 1;i < M;i += sq, j = min(j + sq, M - 1)) {
        S.push_back({ v[i], v[j] });
    }
    for (int j = 1;j < S[0].first;j++) {
        W[Q2[j]] = Q3[j];
    }
    // split into sq block
    for (int L = 0;L < (int)S.size();L++) {
        // Build MST -> O((N/K)mlogm)
        // Queries -> O((K)Qlog(m))
        int i = S[L].first, j = S[L].second;
        if (L != 0) {
            for (int j = S[L - 1].second + 1;j < i;j++) {
                W[Q2[j]] = Q3[j];
            }
        }
        //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 = fr(x.u), pv = fr(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 = fr(U[Q2[x]]), pv = fr(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[fr(x.u)];
            while (!rollback.empty()) {
                auto x = rollback.top();
                rollback.pop();
                sz[x.first] -= sz[x.second];
                p[x.second] = x.second;
            }
        }
        for (auto& l : upd_e) { // Post-Process
            W[Q2[l]] = Q3[l];
        }
    } // m * logm * sqrt(q)
    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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27