Submission #1127328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127328		HossamHero7	Bridges (APIO19_bridges)	C++20	100 / 100	2317 ms	449484 KiB

bridges

// In sha2 Allah IOI 2025
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct DSU{
    vector<int> par;
    vector<int> sz;
    vector<pair<int,int>> rsz;
    vector<int> rpar;
    DSU(int n){
        par.resize(n+1) , sz.resize(n+1,1);
        iota(par.begin(),par.end(),0);
    }
    int getP(int node){
        if(node == par[node]) return node;
        return getP(par[node]);
    }
    bool join(int a,int b){
        a = getP(a) , b = getP(b);
        if(a == b) return 0;
        if(sz[a] < sz[b]) swap(a,b);
        rsz.push_back({a,sz[a]});
        rpar.push_back(b);
        par[b] = a;
        sz[a] += sz[b];
        return 1;
    }
    void rollback(){
        sz[rsz.back().first] = rsz.back().second;
        par[rpar.back()] = rpar.back();
        rsz.pop_back();
        rpar.pop_back();
    }
};
void solve(){
    int n,m;
    cin>>n>>m;
    array<int,3> edges[m];
    for(auto &[a,b,c] : edges) cin>>a>>b>>c;
    int q;
    cin>>q;
    array<int,3> Q[q];
    for(auto &[t,a,b] : Q) cin>>t>>a>>b;
    int ans[q];
    memset(ans,-1,sizeof(ans));
    int changed[m];
    auto cmp = [&](int a,int b){
        return Q[a][2] > Q[b][2];
    };
    auto cmp2 = [&](int a,int b){
        return edges[a][2] > edges[b][2];
    };
    vector<int> un;
    vector<int> qs;
    vector<pair<int,int>> add[q];
    for(int l=0;l<q;l+=2000){
        un.clear() , qs.clear();
        int r = min(q-1,l+1999);
        for(int i=0;i<m;i++) changed[i] = 0;
        vector<int> chh;
        for(int i=l;i<=r;i++){
            if(Q[i][0] == 1) changed[Q[i][1]-1] = 1 , chh.push_back(Q[i][1]-1);
            else qs.push_back(i);
        }
        int lst[m];
        memset(lst,-1,sizeof(lst));
        for(int i=l;i<=r;i++){
            if(Q[i][0] == 2){
                for(auto j : chh){
                    if(lst[j] == -1) add[i].push_back({j,edges[j][2]});
                    else add[i].push_back({j,Q[lst[j]][2]});
                }
            }
            else lst[Q[i][1]-1] = i , edges[Q[i][1]-1][2] = Q[i][2];
        }
        for(int i=0;i<m;i++){
            if(!changed[i]) un.push_back(i);
        }
        sort(un.begin(),un.end(),cmp2);
        sort(qs.begin(),qs.end(),cmp);
        DSU ds(n);
        int pt = 0;
        for(auto idx : qs){
            int w = Q[idx][2] , node = Q[idx][1];
            while(pt < (int)un.size() && edges[un[pt]][2] >= w) ds.join(edges[un[pt]][0],edges[un[pt]][1]) , pt ++;
            int cnt = 0;
            for(auto [e,c] : add[idx]){
                if(c >= w){
                    if(ds.join(edges[e][0],edges[e][1])) cnt ++;
                }
            }
            ans[idx] = ds.sz[ds.getP(node)];
            while(cnt--) ds.rollback();
        }
        
    }
    for(int i=0;i<q;i++){
        if(ans[i] == -1) continue;
        cout<<ans[i]<<endl;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    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