**Problem Summary (USACO Gold 3 February 2016)**

Given a rectangular coordinate plane of dimensions `(A,B)`

, there are `N`

vertical fences, and `M`

horizontal fences. Clearly, the intersection of these fences within the larger rectangle creates `(n+1)(m+1)`

regions.

Given `A,B,N,M`

, the x-coordinates of the `N`

vertical fences and the y coordinates of the `M`

horizontal fences, find the minimum amount of fence to remove to create a minimum spanning tree (connect all regions). In order to remove a fence and thus union two adjacent regions, the entire length of fence between them must be removed.

**Solution**

This is clearly a disjoint-set union problem (union-find/Kruskals), but the tricky part is building the edge-list and tree to union. Each edge is weighted by the length of fence between the two nodes that it connects.

Here is a quick outline of the code below:

1) Read in x,y coords of vertical, horizontal fences (also add 0,0,A,B as “fences”)

2) For each intersection of the fences (some special cases at ends), add the left-facing and up-facing edges to edge list, and additionally add the region between the two edges as a node to the union-find tree.

3) Run Kruskals, keeping track of distance.

This is an O(ElogV) algorithm, which should be more than fast enough since N and M are less than 2000. Note that the given solution (linked above) is fast enough, where this takes to long (failure) for the last 4/10 test cases.

**Where is the performance bottleneck? How can this be improved?**

`#include <iostream> #include <fstream> #include <vector> #include <set> #include <algorithm> #define ll long long using namespace std; const string PROJ_NAME = "fencedin"; struct edge { ll dist; int start; int finish; bool operator< (const edge &rhs) const { return dist < rhs.dist || (!(rhs.dist < dist) && start < rhs.start) || (!(rhs.start < start) && finish < rhs.finish); } }; struct uf_node { int parent; int level; }; ll A, B; int N, M; set<edge> edge_list; vector<uf_node> tree; void make_edge_list(ifstream &fin){ fin >> A >> B >> N >> M; vector<int> vert(N+2); vert[0] = 0; for(int i = 1; i<=N; i++) fin >> vert[i]; vert[N+1] = A; N++; vector<int> hori(M+2); hori[0] = 0; for(int i = 1; i<=M; i++) fin >> hori[i]; hori[M+1] = B; M++; sort(vert.begin(), vert.end()); sort(hori.begin(), hori.end()); tree.resize(N*M); for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ int curr = (i-1)*M+(j-1); //Add node to DSU tree uf_node n = {.parent = curr, .level = 0}; tree[curr] = n; //Add leftward edge if not at bottom if(i != N){ edge left = {.dist = hori[j]-hori[j-1], .start=curr, .finish=curr+M}; edge_list.insert(left); } //Add upward edge if not at right if(j != M){ edge up = {.dist = vert[i]-vert[i-1], .start=curr, .finish=curr+1}; edge_list.insert(up); } } } } int find_par(int i) { if(i != tree[i].parent) { tree[i].parent = find_par(tree[i].parent); } return tree[i].parent; } void do_union(int i, int j) { int r = find_par(i); int s = find_par(j); if(r == s) return; else if (tree[r].level > tree[s].level) { tree[r].parent = s; } else if (tree[s].level > tree[r].level) { tree[s].parent = r; } else { tree[r].parent = s; tree[r].level += 1; } } int main() { ifstream fin (PROJ_NAME + ".in"); ofstream fout (PROJ_NAME + ".out"); make_edge_list(fin); int total_dist = 0; for(edge e: edge_list){ if(find_par(e.start) != find_par(e.finish)){ do_union(e.start, e.finish); total_dist += e.dist; } } fout << total_dist << endl; return 0; } `