USACO Silver 2019 December - Milk Visits

Official Analysis (C++)

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

We perform a search on the tree, identifying connected components of cows that all have the same breed.

In the sample test case, there are $3$ connected components:

• Component $0$: Farms $1$, $2$, and $4$
• Component $1$: Farm $3$
• Component $2$: Farm $5$

Next, we assign the farms in each component a number corresponding to the component they are in. For example, in the sample test case, farm $1$ would get the number $0$, $3$ would get the number $1$, and so on and so forth.

When checking if a visiting farmer going from farm $A$ to $B$ will be happy, there's two possible cases:

1. Farms $A$ and $B$ are part of the same component. This means the path between $A$ and $B$ only contains cows of the same breed. If the farmer prefers milk from this breed, then we should output $1$ and $0$ otherwise.
2. Farms $A$ and $B$ are part of different components. This means that the farmer will always be satisfied because the path between $A$ and $B$ contains both breeds of cows, and so we should always output $1$.

Here's a walkthrough for the sample test case queries:

1. Farms $1$ and $4$ are in the same component, and since Farmer $1$'s preferred cow is Holstein, they will be satisfied. ($1$)
2. Farms $1$ and $4$ are in the same component, but since Farmer $2$'s preferred cow is Guernsey, they will be unsatisfied. ($0$)
3. Farms $1$ and $3$ are in different components, so Farmer $3$ will be satisfied. ($1$)
4. Same logic as query $3$. ($1$)
5. Farm $5$ is Guernsey, and Farmer $5$'s preferred cow is Holstein, they will be unsatisfied. ($0$)

Copy
#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

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

public class MilkVisits {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("milkvisits.in"));

		StringTokenizer initial = new StringTokenizer(read.readLine());
		int farmNum = Integer.parseInt(initial.nextToken());
		int queryNum = Integer.parseInt(initial.nextToken());

Copy
with open("milkvisits.in") as read:
	farm_num, query_num = [int(i) for i in read.readline().split()]
	farms = read.readline()
	neighbors = [[] for _ in range(farm_num)]
	for f in range(farm_num - 1):
		f1, f2 = [int(i) - 1 for i in read.readline().split()]
		neighbors[f1].append(f2)
		neighbors[f2].append(f1)

	queries = []