제출 #1193683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193683		Bui_Quoc_Cuong	Bridges (APIO19_bridges)	C++20	100 / 100	2495 ms	5592 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int SQRT = 700;
#define ALL(A) A.begin(), A.end()

int n, m, q;
struct Edges{
    int u, v, w;
} E[N];
struct Queries{
    int t, u, w;
} Q[N];

struct DisjointSet{
    int lab[N]; 

    struct Data{
        int u, lu, v, lv;
    }; stack <Data> memo;

    int find(int x){
        return lab[x] < 0 ? x : find(lab[x]);
    }

    bool joint(int u, int v){
        int x = find(u), y = find(v);
        if(x == y) return 0;
        if(lab[x] > lab[y]) swap(x, y);

        memo.push({x, lab[x], y, lab[y]});

        lab[x]+= lab[y];
        lab[y] = x;

        return 1;
    }   

    int vers(){
        return memo.size();
    }

    void rollback(int sz){
        while((int)memo.size() > sz){
            lab[memo.top().u] = memo.top().lu;
            lab[memo.top().v] = memo.top().lv;
            memo.pop();
        }
    }

    void clear() {
        for(int i = 1; i <= n; i++){
            lab[i]=-1;
        }
        while(!memo.empty()){
            memo.pop();
        }
    }
} DSU;

bool inQuer[N];
int last[N];
int ans[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define KO ""
    // freopen(KO".inp", "r", stdin);
    // freopen(KO".out", "w", stdout);

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> E[i].u >> E[i].v >> E[i].w;
    }
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> Q[i].t >> Q[i].u >> Q[i].w;
    }

    for(int L = 1; L <= q; L+= SQRT){
        int R = min(q, L + SQRT - 1);

        for(int i = L; i <= R; i++){
            if(Q[i].t == 1){
                inQuer[Q[i].u] = 1;
            }
        }

        vector <int> qry, joint, no_joints;

        for(int i = 1; i <= m; i++){
            if(inQuer[i] == 0){
                no_joints.push_back(i);
            } else{
                joint.push_back(i);
            }
        }

        for (int i = L; i <= R; i++){
            if(Q[i].t == 2){
                qry.push_back(i);
            }
        }

        DSU.clear();

        sort(ALL(no_joints), [&](int u, int v){
            return E[u].w > E[v].w;
        });
        sort(ALL(qry), [&](int u, int v){
            return Q[u].w > Q[v].w;
        });

        int it = 0;

        for(const int &id : qry){
            while(it <= (int)no_joints.size() - 1 && E[no_joints[it]].w >= Q[id].w){
                DSU.joint(E[no_joints[it]].u, E[no_joints[it]].v);
                it++;
            }       

            int ver = DSU.vers();

            for(int i = L; i < id; i++){
                if(Q[i].t == 1){
                    last[Q[i].u] = i;
                }                
            }   

            for(const int &x : joint){
                if(last[x]){
                    if(Q[last[x]].w >= Q[id].w){
                        DSU.joint(E[x].u, E[x].v);
                    }
                } else{
                    if(E[x].w >= Q[id].w){
                        DSU.joint(E[x].u, E[x].v);
                    }
                }
            }

            ans[id] = - DSU.lab[DSU.find(Q[id].u)];

            DSU.rollback(ver);

            for(auto x : joint){
                last[x] = 0;
            }
        }

        for(int i = L; i <= R; i++){
            if(Q[i].t == 1){
                E[Q[i].u].w = Q[i].w;
            }
        }
        for(int i = 1; i <= m; i++){
            inQuer[i] = 0;
        }
    }   

    for(int i = 1; i <= q; i++) if(Q[i].t == 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