Moo Network

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU{
    vector<ll> p;
    DSU(ll n){
        p = vector<ll>(n, -1);
    }
    ll get(ll x){
        if(p[x]<0){
            return x;
        }else{
            return p[x] = get(p[x]);
        }
    }
    bool same_set(ll x, ll y){
        return get(x) == get(y);
    }
    bool unite(ll x, ll y){
        x = get(x);
        y = get(y);
        if(x == y) return false;
        if(p[x]<p[y]) swap(p[x], p[y]);
        p[x]+=p[y];
        p[y] = x;
        return true;
    }
};

struct Coor{
    ll x, y;
    bool operator<(const Coor &a) const{
        if(x==a.x){
            return y<a.y;
        }
        return x<a.x;
    }
};

struct Con{
    ll a;
    ll b;
    ll cost;
    bool operator<(const Con &a) const{
        return cost<a.cost;
    }
};

ll n;
vector<Con> con;
ll ans;

int main(){
    //freopen("moonetwork.in", "r", stdin);

    cin >> n;
    vector<Coor> cd(n);
    //must be n not n+1 because if n+1 then when sorted the values get shifted to the
    //right which result in wrong answer
    for(ll i=0; i<n; i++){
        //int x, y;
        cin >> cd[i].x >> cd[i].y;
    }
    //need to sort to make the values right to use for calculation
    sort(cd.begin(), cd.end());
    vector<ll> last(11, -1);
    //different type of calculation depending on y because y is within 0-10 so can be
    //used while previous looping of n*n would result in run time problem
    for(ll i=0; i<n; i++){
        for(ll j=0; j<=10; j++){
            if(last[j] != -1){
                ll v = last[j];
                ll cost = ((cd[i].x-cd[v].x)*(cd[i].x-cd[v].x))+((cd[i].y-cd[v].y)*(cd[i].y-cd[v].y));
                con.push_back({i, v, cost});
            }
        }
        last[cd[i].y] = i;
    }
    sort(con.begin(), con.end());
    DSU dsu(n+1);
    int count = 0;
    for(ll i=0; i<con.size(); i++){
        if(!dsu.same_set(con[i].a, con[i].b)){
            dsu.unite(con[i].a, con[i].b);
            ans+=con[i].cost;
            count++;
        }
        if(count == n-1){
            break;
        }
    }
    cout << ans << '\n';

    return 0;
}