Submission #1127187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127187		HossamHero7	Bridges (APIO19_bridges)	C++20	59 / 100	3095 ms	5776 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;
    vector<array<int,3>> edges(m);
    for(auto &[a,b,c] : edges) cin>>a>>b>>c;
    int q;
    cin>>q;
    vector<array<int,3>> Q(q);
    for(auto &[t,a,b] : Q) cin>>t>>a>>b;
    vector<int> ans(q,-1);
    int sq = sqrt(q);
    for(int l=0;l<q;l+=sq){
        int r = min(q-1,l+sq-1);
        vector<int> changed(m,1e9);
        vector<pair<int,int>> un;
        vector<array<int,3>> ch_ed;
        vector<array<int,3>> qs;
        for(int i=r;i>=l;i--){
            if(Q[i][0] == 1) ch_ed.push_back({i,changed[Q[i][1]-1],Q[i][2]}) , changed[Q[i][1]-1] = i;
            else qs.push_back({Q[i][2],Q[i][1],i});
        }
        for(int i=0;i<m;i++){
            if(changed[i] == 1e9) un.push_back({edges[i][2],i});
            else ch_ed.push_back({-1,changed[i],edges[i][2]});
        }
        sort(un.rbegin(),un.rend());
        sort(qs.rbegin(),qs.rend());
        DSU ds(n);
        int pt = 0;
        for(auto [w,node,idx] : qs){
            while(pt < (int)un.size() && un[pt].first >= w) ds.join(edges[un[pt].second][0],edges[un[pt].second][1]) , pt ++;
            int cnt = 0;
            for(auto [t,nxt,c] : ch_ed){
                int e = 0;
                if(t == -1) e = Q[nxt][1] - 1;
                else e = Q[t][1] - 1;
                // if(idx == 7){
                //     cout<<"! "<<endl;
                //     cout<<t<<' '<<nxt<<' '<<edges[e][2]<<endl;
                //     cout<<(int)un.size()<<endl;
                // }
                if(t < idx && nxt > idx && c >= w){
                    if(ds.join(edges[e][0],edges[e][1])) cnt ++;
                }
            }
            ans[idx] = ds.sz[ds.getP(node)];
            while(cnt--) ds.rollback();
        }
        
        for(auto [t,nxt,c] : ch_ed){
            if(nxt == 1e9 && t != -1) edges[Q[t][1]-1][2] = Q[t][2];
        }
    }
    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: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27