제출 #1364530

#제출 시각아이디문제언어결과실행 시간메모리
1364530mrasool1665다리 (APIO19_bridges)C++20
0 / 100
27 ms8644 KiB
//MRasool kheyri
//iran -> khorasan -> ferdows -> Baghestan
//14/2/1405
//vasat azmoonima...
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define el '\n'
const ll maxn = 1e6 + 100 ;
ll n , m  , q , par[maxn] , ans[maxn] , sz[maxn] ;
vector<pair<ll,pair<ll,pair<ll,ll>>>> vec ;
ll get_par(ll x){
    if(par[x] == x){
        return x ;
    }
    par[x] = get_par(par[x]) ;
    return par[x] ;
}
void solve(){
    cin>>n>>m ;
    for(ll i = 0 ; i < m ; i++){
        ll u , v , d ;
        cin>>u>>v>>d ;
        u-- , v-- ;
        vec.push_back({d,{1,{u,v}}}) ;
    }
    cin>>q ;
    for(ll i = 0 ; i < q ; i++){
        ll typ ;
        cin>>typ ;
        if(typ == 1){return;}
        ll x , d ;
        cin>>x>>d ;
        x-- ;
        vec.push_back({d,{0LL,{i,x}}}) ;
    }
    for(ll i = 0 ; i < n ; i++){
        par[i] = i ;
        sz[i] = 1 ;
    }
    for(ll i = vec.size()-1 ; i >= 0 ; i--){
        if(vec[i].second.first == 1){
            ll u = vec[i].second.second.first , v = vec[i].second.second.second ;
            if(get_par(u) != get_par(v)){
                sz[get_par(v)] += sz[get_par(u)] ;
                sz[get_par(u)] = 0 ;
                par[get_par(u)] = get_par(v) ;
            }
        }
        else{
            ll i = vec[i].second.second.first , u = vec[i].second.second.second ;
            ans[i] = sz[get_par(u)] ;
        }
    }
    for(ll i = 0 ; i < q ; i++){
        cout<<ans[i]<<el ;
    }
    return ;
}
int main(){
    ios_base::sync_with_stdio(0) , cin.tie(nullptr) , cout.tie(nullptr) ;
    ll t = 1 ;
    //cin>>t ;
    while(t--){
        solve() ;
    }
    return 0 ;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…