USACO Silver 2020 December - Cowntagion

Authors: Kevin Sheng (Java, Python), Tanish Tyagi (C++), Melody Yu (Video)

Edit This Page

Official Editorial

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

Solution 1 - Math

Time Complexity: O(N)\mathcal O(N)

Implementation

Java

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


public class Cowntagion {
	@SuppressWarnings("unchecked")
	// don't worry, i totally know what i'm doing
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int farmNum = Integer.parseInt(read.readLine());
		List<Integer>[] neighbors = new ArrayList[farmNum];

Python

from collections import deque


# straight from stackoverflow
def ceil_log_2(x):  # returns the smallest n so that 2^n >= x
	return 1 if x == 0 else (x - 1).bit_length()




num_farms = int(input())
neighbors = [[] for _ in range(num_farms)]
for _ in range(num_farms - 1):

Solution 2 - DFS

Time Complexity: O(N)\mathcal O(N)

Implementation

C++

#include <bits/stdc++.h>


using namespace std;


#define maxn 100005


int n;
vector<int> adj[maxn];


int dfs(int start, int parent) {

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