제출 #1322613

#제출 시각아이디문제언어결과실행 시간메모리
1322613Newtonabc다리 (APIO19_bridges)C++20
59 / 100
3094 ms4700 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int SQ=320;
int u[N],v[N],w[N],t[N],x[N],y[N],pa[N],sz[N],ans[N];
stack<int> st;
bool ch[N];
vector<int> add[N];
int root(int x){if(pa[x]==x) return x; return root(pa[x]);}
void roll(int x){
    while(st.size()>x){
        int u=st.top();
        sz[pa[u]]-=sz[u];
        pa[u]=u;
        st.pop();
    }
}
void mer(int a,int b){
    a=root(a),b=root(b);
    if(a==b) return;
    if(sz[a]>sz[b]) swap(a,b);
    sz[b]+=sz[a];
    pa[a]=b;
    st.push(a); 
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m; cin>>n >>m;
    for(int i=1;i<=m;i++) cin>>u[i] >>v[i] >>w[i];
    int q; cin>>q;
    for(int i=0;i<q;i++) cin>>t[i] >>x[i] >>y[i];
    for(int i=1;i<=n;i++) pa[i]=i;
    for(int l=0;l<q;l+=SQ){
        int r=min(l+SQ-1,q-1);
        for(int i=1;i<=n;i++) pa[i]=i,sz[i]=1;
        while(!st.empty()) st.pop();
        for(int i=1;i<=m;i++) ch[i]=false;
        vector<int> unc,s;
        for(int i=l;i<=r;i++){
            if(t[i]==1) ch[x[i]]=true;
            else s.push_back(i);
        }
        vector<int> upd;
        for(int i=1;i<=m;i++){
            if(ch[i]==0) unc.push_back(i);
            else upd.push_back(i);
        }
        sort(unc.begin(),unc.end(),[&](int a,int b){
            return w[a]>w[b];
        });
        sort(s.begin(),s.end(),[&](int a,int b){
            return y[a]>y[b];
        });
        for(int i=l;i<=r;i++){
            if(t[i]==1){
                w[x[i]]=y[i];
            }
            else{
                for(auto j:upd) if(w[j]>=y[i]) add[i-l].push_back(j);
            }
        }
        int ptr=0;
        for(auto i:s){
            while(ptr<unc.size() && w[unc[ptr]]>=y[i]){
                mer(u[unc[ptr]],v[unc[ptr]]);
                ptr++;
            }
            int psz=st.size();
            for(auto j:add[i-l]) mer(u[j],v[j]);
            ans[i]=sz[root(x[i])];
            roll(psz);
        }
        for(int i=l;i<=r;i++) add[i-l].clear();
    }
    for(int i=0;i<q;i++) if(t[i]!=1) 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...