Table of Contents

ExplanationImplementation

Official Analysis (Java)

Explanation

We want to find the number of pairs of cows for which crossing at least one road is necessary for one cow to visit the other.

Let's consider an arbitrary cow. By performing either BFS or DFS, we can determine which squares that cow can reach without crossing any roads. Then, we can determine which cows cannot be visited without crossing any roads by checking if that cow's square is reachable.

Finally, to determine all such pairs of cows, we can perform BFS or DFS for each cow and compute the number of unreachable cows, making sure to avoid double-counting pairs.

Implementation

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

C++

Note that using set here instead of unordered_set adds an extra log⁡R\log R factor to the time complexity.

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


struct Road {
	int sr, sc;
	int er, ec;
};


/** to use the struct in a set, a comparator must be implemented. */
inline bool operator<(const Road &r1, const Road &r2) {

Java

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


public class CountCross {
 	Code Snippet: Road Class (Click to expand)


	private static int sideLen;
	private static Set<Road> roads = new HashSet<>();
	private static boolean[][] hasCow;
	private static boolean[][] visited;

Python

from typing import List, Tuple




def neighbors(r: int, c: int) -> List[Tuple[int, int]]:
	""":return: the 4 cardinal neighbors of a position"""
	return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]




with open("countcross.in") as read:
	side_len, cow_num, road_num = [int(i) for i in read.readline().split()]

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