Submission #1168415

#TimeUsernameProblemLanguageResultExecution timeMemory
1168415thinknoexitBridges (APIO19_bridges)C++20
0 / 100
3092 ms7168 KiB
#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(n) block
    int sq = sqrt(n);
    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 (int j = upd_e.size() - 1;j >= 0;j--) {
                if (upd_e[j] <= t) break;
                W2[upd_e[j]] = W[upd_e[j]];
            }
            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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...