제출 #1347730

#제출 시각아이디문제언어결과실행 시간메모리
1347730goodpjw2008Bridges (APIO19_bridges)C++20
100 / 100
2936 ms8920 KiB
#include <bits/stdc++.h>
using namespace std;

struct dsu{
    int par[50002],sz[50002];
    vector<tuple<int,int,int>>v;
    void init(int n){
        for(int i = 1; i <= n; i++){
            par[i]=i;
            sz[i]=1;
        }
        v.clear();
    }
    int find(int x){
        if(par[x]==x)return x;
        return find(par[x]);
    }
    void rollback(){
        if(v.empty())return;
        auto [x,y,z]=v.back();
        v.pop_back();
        par[x]=x;
        sz[y]=z;
    }
    bool merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return false;
        if(sz[x]>sz[y])swap(x,y);
        par[x]=y;
        v.push_back({x,y,sz[y]});
        sz[y]+=sz[x];
        return true;
    }
}D;
struct p{
    int x,y,val;
}inp[100002];
int blk=316;
struct query{
    int q,a,b;
}qu[100002];
int change[100002];
struct query2{
    int q,a,b,idx;
};
bool chk[100002];
int ans[100002];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,q;
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        cin>>inp[i].x>>inp[i].y>>inp[i].val;
    }
    cin>>q;
    for(int i = 1; i <= q; i++){
        cin>>qu[i].q>>qu[i].a>>qu[i].b;
    }
    for(int i = 1; i <= q; i+=blk){
        D.init(n);
        memset(change,0,sizeof(change));
        vector<query2>v;
        vector<int>idxs;
        for(int j = 0; j < blk&&i+j<=q; j++){
            if(qu[i+j].q==1)change[qu[i+j].a]=1;
            else v.push_back({2,qu[i+j].a,qu[i+j].b,i+j});
        }
        for(int j = 1; j <= m; j++){
            if(!change[j])v.push_back({1,-1,inp[j].val,j});
            else idxs.push_back(j);
        }
        sort(v.begin(),v.end(),[](query2 &a,query2 &b){
            if(a.b==b.b)return a.q<b.q;
            return a.b>b.b;
        });
        for(auto &[qq,a,b,idx]:v){
            if(qq==1)D.merge(inp[idx].x,inp[idx].y);
            else{
                int initsz=D.v.size();
                for(int j = idx-1; j >= i; j--){
                    if(qu[j].q==1&&qu[j].b>=b&&!chk[qu[j].a]){
                        D.merge(inp[qu[j].a].x,inp[qu[j].a].y);
                    }
                    if(qu[j].q==1)chk[qu[j].a]=1;
                }
                for(int j : idxs){
                    if(!chk[j]&&inp[j].val>=b){
                        D.merge(inp[j].x,inp[j].y);
                    }
                }
                ans[idx]=D.sz[D.find(a)];
                for(int j = idx-1; j >= i; j--){
                    if(qu[j].q==1)chk[qu[j].a]=0;
                }
                while(D.v.size()>initsz){
                    D.rollback();
                }
            }
        }
        for(int j = 0; j < blk&&i+j<=q; j++){
            if(qu[i+j].q==1)inp[qu[i+j].a].val=qu[i+j].b;
        }
    }
    for(int i = 1; i <= q; i++){
        if(qu[i].q==2)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...