Fenced In

    1#include<bits/stdc++.h>
    2using namespace std;
    3int A, B, n, m;
    4int ver[2010], hor[2010], v[2010], h[2010];
    5vector<tuple<int, int, int>> edges;
    6long long ans = 0;
    7struct DSU {
    8vector<int> e;
    9DSU(int N) {
    10   e = vector<int>(N, -1);
    11}
    12 
    13 
    14// get representive component (uses path compression)
    15int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
    16 
    17 
    18bool same_set(int a, int b) { return get(a) == get(b); }
    19 
    20 
    21int size(int x) { return -e[get(x)]; }
    22 
    23 
    24bool unite(int x, int y) {  // union by size
    25 x = get(x), y = get(y);
    26 if (x == y) return false;
    27 if (e[x] > e[y]) swap(x, y);
    28 e[x] += e[y];
    29 e[y] = x;
    30 return true;
    31}
    32};
    33int main(void){
    34 
    35 
    36   ifstream cin("fencedin.in");
    37   ofstream cout("fencedin.out");
    38 
    39 
    40   cin >> A >> B >> n >> m;
    41 
    42 
    43   for(int i = 0; i < n; i++){
    44       cin >> v[i];
    45   }
    46   v[n] = 0;
    47   v[n+1] = A;
    48 
    49 
    50   for(int i = 0; i < m; i++){
    51       cin >> h[i];
    52   }
    53   h[m] = 0;
    54   h[m+1] = B;
    55 
    56 
    57   sort(v, v+n+2);
    58   sort(h, h+m+2);
    59 
    60 
    61   for(int i = 0; i <= m; i++){
    62       int deltay = h[i+1]-h[i];
    63       for(int j = 0; j < n; j++){
    64           int a = i*(n+1)+j;
    65           int b = i*(n+1)+j+1;
    66           edges.push_back(tie(deltay, a, b));
    67       }
    68   }
    69 
    70 
    71   for(int i = 0; i <= n; i++){
    72       int deltax = v[i+1]-v[i];
    73       for(int j = 0; j < m; j++){
    74           int a = j*(n+1)+i;
    75           int b = (j+1)*(n+1)+i;
    76           edges.push_back(tie(deltax, a, b));
    77       }
    78   }
    79 
    80 
    81   sort(edges.begin(), edges.end());
    82 
    83 
    84   DSU du((n+1)*(m+1));
    85 
    86 
    87   for(auto u: edges){
    88       if(du.unite(get<1>(u), get<2>(u))){
    89           ans += get<0>(u);
    90           
    91           // if(du.size(get<1>(u)) == (n+1)*(m+1)){
    92           //     cout << ans << endl;
    93           //     return 0;
    94           // }
    95       }
    96   }
    97 
    98 
    99   cout << ans << endl;
    100 
    101 
    102   return 0;
    103}
    104 
    105