USACO Silver 2021 December - Connecting Two Barns

Official Analysis (C++)

Implementation - DFS + Two Pointers

Time Complexity: $\mathcal{O}(T\cdot (N + M))$

Copy
import java.io.*;
import java.util.*;

public class ConnectingTwoBarns {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int t = io.nextInt();
		for (int test = 0; test < t; test++) {
			int n = io.nextInt();
			int m = io.nextInt();

Alternative Implementation - DFS + Binary Search

As the editorial mentioned, we can minimize the cost function by using binary search. Since each conncected component array is in sorted order (if we add the nodes of each connected component in increasing order), we can binary search on the sorted connected component array to find the closest field $j$ for each field $i$ using std::lower_bound.

Copy
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX_N = 1e5;

vector<int> adj[MAX_N];
// List of all the components of the farm
vector<int> comps[MAX_N];