Submission #1350697

#TimeUsernameProblemLanguageResultExecution timeMemory
1350697nguyenkhangninh99Bridges (APIO19_bridges)C++20
100 / 100
2581 ms59524 KiB
#include <bits/stdc++.h>
using namespace std;

const int B = 400;
struct DSU{
    vector<int> sz, p;
    vector<array<int, 2>> hist;

    void init(int n){
        p.resize(n + 1);
        for(int i = 1; i <= n; i++) p[i] = i;
        sz.assign(n + 1, 1);
    }
    int get(int u){
        return (u == p[u] ? u : get(p[u]));
    }
    void update(int u, int v, int c){
        u = get(u), v = get(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        if(c) hist.push_back({u, v});
        sz[u] += sz[v];
        p[v] = u;
    }
    void del(){
        while(hist.size()){
            auto [u, v] = hist.back();
            hist.pop_back();
            sz[u] -= sz[v];
            p[v] = v;
        }
    }
} dsu;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
     int n, m; cin >> n >> m;
    vector<int> u(m + 1), v(m + 1), w(m + 1);
    for(int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];

    int q; cin >> q;
    vector<array<int, 3>> query(q + 1);
    for(int i = 1; i <= q; i++) for(int j = 0; j <= 2; j++) cin >> query[i][j];
    dsu.init(n);

    vector<int> ans(q + 1), change(m + 1);
    vector<vector<int>> add(q + 1);
    for(int l = 1; l <= q; l += B){
        int r = min(l + B - 1, q);
        vector<array<int, 3>> order;
        vector<int> update;
        for(int i = l; i <= r; i++){
            if(query[i][0] == 1){
                change[query[i][1]] = 1;
                update.push_back(query[i][1]);
            }
            else order.push_back({query[i][2], i - q, query[i][1]});
        }
        for(int i = 1; i <= m; i++){
            if(!change[i]) order.push_back({w[i], u[i], v[i]});
        }
        sort(order.rbegin(), order.rend());
        for(int i = l; i <= r; i++){
            if(query[i][0] == 1) w[query[i][1]] = query[i][2];
            else{
                for(int x: update){
                    if(w[x] >= query[i][2]) add[i].push_back(x);
                }
            }
        }
        for(auto [w, i, j]: order){
            if(i <= 0){
                for(int k: add[i + q]) dsu.update(u[k], v[k], 1);
                ans[i + q] = dsu.sz[dsu.get(j)];
                dsu.del();
            }
            else dsu.update(i, j, 0);
        }
        for(int i = l; i <= r; i++){
            if(query[i][0] == 1) change[query[i][1]] = 0;
        }
        dsu.init(n);
    }

    for(int i = 1; i <= q; i++){
        if(query[i][0] == 2) cout << ans[i] << "\n";
   }
}
#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...