Official Analysis (Python)

Explanation

Let's first think about how to determine if a cow can go from $(x_1, y_1)$ at time $t_1$ to $(x_2, y_2)$ at time $t_2$.

The shortest path a cow can take is the straight line connecting $(x_1, y_1)$ to $(x_2, y_2)$, which has a length of

by the distance formula.

Now, the cow's journey is possible if and only if this length is no greater than $t_2 - t_1$. In other words, we have the following inequality:

Therefore, we can check if the inequality holds for each cow and grazing site, and if every grazing site satisfies the inequality for a particular cow, then it is a suspect. Otherwise, it must be innocent.

Now, rather than using brute force to iterate through all cows and grazing sites, we use the condition that a cow can reach any grazing site from another within the specified times.

Consider a cow at $(x_1, y_1)$ at time $t_1$ and two grazing sites at $(x_2, y_2)$ and $(x_3, y_3)$ at times $t_2$ and $t_3$, where $t_1 < t_2 < t_3$. If the cow can reach the grazing site at $(x_2, y_2)$, then it can also reach the grazing site at $(x_3, y_3)$. The same is true when $t_1 > t_2 > t_3$.

This means that for each cow, we only need to check the two grazing sites with times closest to their reported time! We can find these two sites by sorting the list of grazing sites by time and using binary search, which is fast enough to solve the problem.

Implementation

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

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

struct Event {
	int t, x, y;

	bool operator<(const Event &other) const { return t < other.t; }
};

Event read() {

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

public class CowLibi {
	private static class Event implements Comparable<Event> {
		int t, x, y;

		private Event(int t, int x, int y) {
			this.t = t;
			this.x = x;

Copy
import bisect
from typing import Tuple

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


def read():
	x, y, t = map(int, input().split())
	return t, x, y