Submission #1332177

#TimeUsernameProblemLanguageResultExecution timeMemory
1332177Warinchai다리 (APIO19_bridges)C++17
0 / 100
3108 ms362688 KiB
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,pair<int,int>>>e;
stack<pair<int,pair<int,int>>>s;

int p[50005];
int sz[50005];
int ans[100005];
int used[100005];
int sq=0;

int fp(int a){
    if(p[a]==a)return a;
    return fp(p[a]);
}

void un(int a,int b){
    a=fp(a),b=fp(b);
    if(sz[a]<sz[b])swap(a,b);
    s.push({b,{sz[b],a}});
    if(a==b)return;
    sz[a]+=sz[b];
    p[b]=a;
}

void rollback(){
    auto x=s.top();
    s.pop();
    sz[x.first]=x.second.first;
    p[x.first]=x.first;
    sz[x.second.second]-=x.second.first;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,d;cin>>u>>v>>d;
        e.push_back({d,{u,v}});
    }
    int q;cin>>q;
    sq=sqrt(q);
    //cerr<<"SQ:"<<sq<<" "<<q<<"\n";
    vector<pair<int,pair<int,int>>>qr;
    vector<pair<int,pair<int,pair<int,int>>>>qr2;
    int cnt=0;
    for(int i=1;i<=n;i++)sz[i]=1,p[i]=i;
    int stcnt=cnt;
    for(int i=1;i<=q;i++){
        //cerr<<"\n";
        int t;cin>>t;
        int ccur=0;
        //cerr<<"stcnt:"<<stcnt<<"\n";
        if(t==2){
            int a,b;cin>>a>>b;
            qr.push_back({b,{a,++cnt}});
            ccur++;
            qr2.push_back({t,{a,{b,ccur}}});
        }else{
            int a,b;cin>>a>>b;
            qr2.push_back({t,{a,{b,ccur}}});
            used[a]=1;
        }
        //cerr<<"i:"<<i<<"\n";
        if(i%sq==0||i==q){
            for(int i=1;i<=n;i++)sz[i]=1,p[i]=i;
            //cerr<<"do:"<<i<<"\n";
            vector<vector<pair<int,int>>>ee(sq+5);
            vector<pair<int,pair<int,int>>>te;
            vector<int>ue;
            for(int j=1;j<=m;j++)if(used[j]==1)ue.push_back(j);
            /*cerr<<"used:\n";
            for(int j=1;j<=m;j++)cerr<<used[j]<<" ";
            cerr<<"\n";
            for(int j=1;j<=m;j++)cerr<<e[j-1].first<<" ";
            cerr<<"\n";*/
            int tcnt=0;
            for(auto x:qr2){
                if(x.first==1){
                    e[x.second.first-1].first=x.second.second.first;
                }else{
                    //cerr<<"compute qr2:"<<x.second.first<<' '<<x.second.second.first<<'\n';
                    vector<pair<int,int>>temp;
                    for(auto xx:ue){
                        //cerr<<e[xx-1].first<<'\n';
                        if(e[xx-1].first>=x.second.second.first)temp.push_back(e[xx-1].second);
                    }
                    ee[x.second.second.second]=temp;
                    //cerr<<"edges used:"<<x.second.second.second<<"\n";
                    //for(auto x:temp)cerr<<x.first<<' '<<x.second<<"\n";
                }
            }
            //cerr<<"qr2 work\n";
            for(int j=1;j<=m;j++)if(used[j]==0){
                te.push_back(e[j-1]);
            }
            sort(qr.begin(),qr.end());
            reverse(qr.begin(),qr.end());
            sort(te.begin(),te.end());
            reverse(te.begin(),te.end());
            int cur=0,cur2=0;
            //cerr<<"qrbf work\n";
            for(auto x:qr){
                //cerr<<"doing:"<<x.first<<' '<<x.second.first<<" "<<x.second.second<<"\n";
                while(cur<te.size()&&te[cur].first>=x.first){
                    //cerr<<"un:"<<te[cur].second.first<<' '<<te[cur].second.second<<" "<<te[cur].first<<"\n";
                    un(te[cur].second.first,te[cur].second.second);
                    cur++;
                }
                //cerr<<"done un1\n";
                cur2=x.second.second-stcnt;
                //cerr<<"cur2:"<<cur2<<"\n";
                //cerr<<x.second.second<<"-"<<stcnt<<"-1"<<"\n";
                for(auto xx:ee[cur2]){
                    //cerr<<"un:"<<xx.first<<' '<<xx.second<<"\n";
                    un(xx.first,xx.second);
                }
                ans[x.second.second]=sz[fp(x.second.first)];
                for(auto xx:ee[cur2]){
                    rollback();
                }
                cur2++;
            }
            //cerr<<"qr work\n";
            for(int j=1;j<=m;j++)used[j]=0;
            qr.clear();
            qr2.clear();
            stcnt=cnt;
        }
        //cerr<<"work\n";
    }
    for(int i=1;i<=cnt;i++){
        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...