Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define MAXN 112345
- #define INF LLONG_MAX
- #define double long double
- #define int long long
- #define pii pair<long long,long long>
- #define f first
- #define s second
- #define mp make_pair
- #define eps 1e-11
- #define pi acos(-1)
- #define MOD 1000000007
- int n;
- int pai[MAXN],peso[MAXN];
- int find(int x){
- return pai[x]=(x==pai[x]?x:find(pai[x]));
- }
- void join(int x,int y){
- if((x=find(x))==(y=find(y)))return;
- if(peso[x]<peso[y])swap(x,y);
- peso[x]+=peso[y];pai[y]=x;
- }
- void init(){
- for(int i=0;i<n;i++)peso[pai[i]=i]=1;
- }
- pii val[MAXN];
- int32_t main(){
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.precision(9);
- cout.setf(ios::fixed);
- int m;
- cin>>n>>m;
- for(int i=0;i<n;i++){
- cin>>val[i].f;
- val[i].s=i;
- }
- sort(val,val+n);
- vector<pair<int,pii>> edges;
- for(int i=0;i<n-1;i++)
- edges.pb(mp(val[i].f-val[i+1].f,mp(val[i].s,val[i+1].s)));
- for(int i=0;i<m;i++){
- int a,b;
- cin>>a>>b;
- a--;b--;
- join(a,b);
- }
- sort(edges.begin(),edges.end());
- int resp=0;
- for(auto x:edges){
- if(find(x.s.f)!=find(x.s.s)){
- join(x.s.f,x.s.s);
- resp+=x.f*x.f;
- }
- }
- cout<<resp<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement