USACO Silver 2021 December - Connecting Two Barns

Authors: Nathan Gong, Jesse Choe, Ricky Zhang

Edit This Page

Official Analysis (C++)

Implementation - DFS + Two Pointers

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

C++

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


using ll = long long;


int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, m;

Java

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 also minimize the cost function by using binary search. The connected component arrays are in sorted order (since we are adding nodes in order from 11 to NN), so we can binary search on the sorted connected component array to find the closest field jj for each field ii using std::lower_bound.

C++

#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];

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum