Submission #1186785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186785		irmuun	Bridges (APIO19_bridges)	C++20	100 / 100	1461 ms	10232 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=5e4+5,M=1e5+5,Q=1e5+5;

int n,m,q;
vector<int>g[N];
int u[M],v[M],w[M];
int t[Q],x[Q],y[Q];

int sz[N],par[N];
vector<int>st;

void init(){
    fill(sz,sz+n,1);
    iota(par,par+n,0);
    st.clear();
}

int find(int x){
    while(x!=par[x]) x=par[x]; //atmost logN times
    return x;
}

void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    par[y]=x;
    sz[x]+=sz[y];
    st.pb(y);
}

void roll_back(int rem){
    while(st.size()>rem){
        int y=st.back();
        int x=par[y];
        sz[x]-=sz[y];
        par[y]=y;
        st.pop_back();
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>u[i]>>v[i]>>w[i];
        u[i]--,v[i]--;
    }
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>t[i]>>x[i]>>y[i];
        x[i]--;
    }
    int B=1000;
    bool changed[m];
    vector<int>join[B];
    int ans[Q];
    for(int l=0;l<q;l+=B){
        init();
        int r=min(q,l+B);
        fill(changed,changed+m,false);
        vector<int>ask,upd;
        for(int i=l;i<r;i++){
            if(t[i]==1){
                changed[x[i]]=true;
            }
            else{
                ask.pb(i);
            }
        }
        vector<int>edge,left;
        for(int i=0;i<m;i++){
            if(changed[i]==true){
                upd.pb(i);
            }
            else{
                edge.pb(i);
            }
        }
        for(int i=l;i<r;i++){
            if(t[i]==1){
                w[x[i]]=y[i];
            }
            else{
                join[i-l].clear();
                for(int j:upd){
                    if(w[j]>=y[i]){
                        join[i-l].pb(j);
                    }
                }
            }
        }
        sort(all(edge),
            [&](int i,int j){
                return w[i]>w[j];
            }
        );
        sort(all(ask),
            [&](int i,int j){
                return y[i]>y[j];
            }
        );
        int j=0;
        for(int i:ask){
            while(j<edge.size()&&w[edge[j]]>=y[i]){
                merge(u[edge[j]],v[edge[j]]);
                j++;
            }
            int rem=st.size();
            for(int e:join[i-l]){
                merge(u[e],v[e]);
            }
            ans[i]=sz[find(x[i])];
            roll_back(rem);
        }
    }
    for(int i=0;i<Q;i++){
        if(t[i]==2){
            cout<<ans[i]<<"\n";
        }
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27