USACO Gold 2018 January - Cow At Large

Official Analysis

Suppose that a given farmer reaches Bessie at barn $i$; this is only possible if that farmer reached barn $i$ either:

• At the same time as Bessie
• At an earlier time than Bessie

This means that we can treat this problem as a shortest path problem, where the farmer reaches barn $i$ at the same time or earlier than Bessie if $\texttt{dist1[i]} \leq \texttt{dist2[i]}$. Here, $\texttt{dist1[i]}$ represents the shortest distance between any given farmer and the $i$-th barn, and $\texttt{dist2[i]}$ represents the shortest distance between Bessie and the $i$-th barn. Note that $\texttt{dist2[i]}$ can also be represented as the tree depth at barn $i$ with the tree rooted at barn $k$.

We can run BFS to find $\texttt{dist1[i]}$ and DFS or BFS to find $\texttt{dist2[i]}$. Once we find these shortest distances, we can simulate Bessies' movement by "catching" her when $\texttt{dist1[i]} \leq \texttt{dist2[i]}$. Once Bessie is caught, we can stop her movement and increase the total number of farmers by 1. This greedily finds the minimum number of farmers, since we only store the "optimal" farmers in our answer.

Implementation

Time Complexity: $\mathcal{O}(V+E)$

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

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;

#define pb push_back
#define f first
#define s second

Copy
from collections import deque

with open("atlarge.in", "r") as infile:
	n, k = map(int, infile.readline().split())
	graph = [[] for _ in range(n)]
	for _ in range(n - 1):
		f, t = map(lambda i: int(i) - 1, infile.readline().split())
		graph[f].append(t)
		graph[t].append(f)

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

public class AtLarge {
	static int N, K, A = 0;
	static List<Integer>[] adj;
	static int[] depth, leaf, inDeg, parent;
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("atlarge");