CUBE-T184: Worker

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int w, u, v;
    edge(int weight, int st, int ed){
        w = weight;
        u = st;
        v = ed;
    }
    bool operator < (const edge &rhs) const{
        if(w != rhs.w){
            return w < rhs.w;
        } else if(u != rhs.u){
            return u < rhs.u;
        } else {
            return v < rhs.v;
        }
    }
};

typedef long long lli;

const int N = 1000;

int ds[N + 1], sz[N + 1];
int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

void dsUnion(int u, int v){
    if(sz[u] < sz[v]){
        swap(u, v);
    }
    ds[v] = u;
    sz[v] += sz[u];
}

vector<edge> edges;
int hatred[N + 1];

int main(){

    int nPeople;
    scanf("%d", &nPeople);

    // DSU Setup
    for(int i = 0; i <= nPeople; ++i){
        ds[i] = i;
        sz[i] = 1;
    }

    for(int i = 1; i <= nPeople; ++i){
        int talk;
        scanf("%d", &talk);
        edges.emplace_back(talk, 0, i);
    }
    for(int i = 1; i <= nPeople; ++i){
        scanf("%d", &hatred[i]);
    }
    for(int u = 1; u <= nPeople - 1; ++u){
        for(int v = u + 1; v <= nPeople; ++v){
            edges.emplace_back(hatred[u] + hatred[v], u, v);
        }
    }
    sort(edges.begin(), edges.end());

    lli sum = 0;
    for(edge e : edges){
        int w = e.w;
        int u = e.u;
        int v = e.v;
        u = dsFind(u);
        v = dsFind(v);
        if(u != v){
            sum += w;
            dsUnion(u, v);
            bool connected = true;
            for(int i = 0; i < nPeople; ++i){
                if(dsFind(i) != dsFind(i + 1)){
                    connected = false;
                    break;
                }
            }
            if(connected){
                break;
            }
        }
    }
    cout << sum;

    return 0;
}