제출 #1332145

#제출 시각아이디문제언어결과실행 시간메모리
1332145WarinchaiBridges (APIO19_bridges)C++17
14 / 100
63 ms4316 KiB
#include<bits/stdc++.h>
using namespace std;

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

int p[50005];
int sz[50005];
int ans[100005];

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(a==b)return;
    if(sz[a]<sz[b])swap(a,b);
    sz[a]+=sz[b];
    p[b]=a;
}

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;
    vector<pair<int,pair<int,int>>>qr;
    int cnt=0;
    for(int i=1;i<=n;i++)sz[i]=1,p[i]=i;
    for(int i=0;i<q;i++){
        int t;cin>>t;
        if(t==2){
            int a,b;cin>>a>>b;
            qr.push_back({b,{a,++cnt}});
        }else{
            int a,b;cin>>a>>b;
        }
    }
    sort(qr.begin(),qr.end());
    reverse(qr.begin(),qr.end());
    sort(e.begin(),e.end());
    reverse(e.begin(),e.end());
    int cur=0;
    for(auto x:qr){
        while(cur<e.size()&&e[cur].first>=x.first){
            un(e[cur].second.first,e[cur].second.second);
            cur++;
        }
        ans[x.second.second]=sz[fp(x.second.first)];
    }
    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...