Official Analysis (C++)

In this problem, we are asked to determine if all remaining barns are connected as the barns close one at a time. To check this, we can run a depth-first search (DFS) starting from the barn that will close last. To simulate the closure of each barn, we can store a boolean array and set each barn in the iteration to be "closed". Then, we can run the DFS and check how many nodes have been visited. If all the unclosed nodes have been visited, then we print "YES" otherwise, we print "NO".

Implementation

Time Complexity: O(N2+NM)\mathcal{O}(N^2 + NM)

Python

Warning: Time Limit Exceeded

Since Python is slow, it exceeds the time limit on test cases 8 and 10 even though the solution is the intended one.

import sys


sys.stdin = open("closing.in", "r")
sys.stdout = open("closing.out", "w")


n, m = map(int, input().split())


adj, order = {}, []
for i in range(1, n + 1):
	adj[i] = []

C++

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;


int n, m;
const int MAX_N = 3000;


vector<vector<int>> adj(MAX_N);
vector<int> vis(MAX_N);

Java

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


public class closing {
	// Store global variables used by dfs
	static ArrayList<ArrayList<Integer>> adj;
	static boolean[] visited, closed;
	static int nodes;


	public static void main(String[] args) throws IOException {

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