Submission

[PPPPPPPPPP][PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Monasm

Problemset: E.Kingdom

Language: cpp

Time: 0.257 second

Submitted On: 2025-01-08 17:47:54

#include <bits/stdc++.h>

#define int long long int
#define pii pair<int,int>
using namespace std;

int find(vector<int> &p,int x){
    if(p[x] == x)return x;
    return p[x] = find(p,p[x]);
}

void join(vector<int> &p,int a,int b){
    a = find(p,a);
    b = find(p,b);
    p[b] = a;
}

int32_t main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,k,ans,mina=1e18,maxb=0,cnt=0;cin>>n>>m>>k;
    vector<int> p(n);
    vector<pair<int,pii>> a,b;
    for(int i=0;i<n;i++)p[i]=i;
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        if(w>=k){
            a.push_back({w,{u,v}});
            mina=min(w,mina);
        }
        else{
            b.push_back({w,{u,v}});
            maxb=max(w,maxb);
        }
    }
    sort(b.begin(),b.end());
    for(int i=a.size()-1;i>=0;i--){
        int w=a[i].first,u=a[i].second.first,v=a[i].second.second;
        if(find(p,u)!=find(p,v)){
            cnt++;
            join(p,u,v);
        }
    }
    if(cnt==n-1){
        if(b.size()){
            ans=abs(maxb-k)<=abs(mina-k)?abs(maxb-k)+(m-a.size()-1):abs(mina-k)+(m-a.size());
        }
        else{
            ans=min(abs(mina-k),k)+(m-a.size());
        }
        cout<<ans;
        return 0;
    }
    ans=0;
    for(int i=b.size()-1;i>=0;i--){
        int w=b[i].first,u=b[i].second.first,v=b[i].second.second;
        if(find(p,u)!=find(p,v)){
            join(p,u,v);
            ans+=abs(w-k);
            cnt++;
        }
        else{
            ans++;
        }
    }
    cout<<ans+((n-1-cnt)*k);
}