(Analysis by Andi Qu)

First, let's 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 $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$ due to the Pythagorean theorem. The cow's journey is possible if and only if this length is no greater than $t_2 - t_1$. This condition can be summarized in the following inequality:

$$(t_2 - t_1)^2 \geq (x_2 - x_1)^2 + (y_2 - y_1)^2$$

Using this fact, we can solve subtask 1 using the following $O(GN)$ algorithm:

• Iterate through the list of cows and grazing sites in two nested loops.
• For each cow and grazing site, check if the inequality holds.
• If every grazing site satisfies the inequality for a particular cow, then it is a suspect; otherwise, it must be innocent.

To speed up this algorithm, we use the condition that a cow can go from any grazing site to 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 make it to the grazing site at $(x_2, y_2)$, then it can also make it to 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 efficiently by sorting the list of grazing sites by time and using binary search, which gives us an $O((N + G) \log G)$ algorithm.

Ben's code in Python:

import bisect
G, N = map(int, input().split())

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

grazings = sorted([read() for _ in range(G)])
ans = 0

def reachable(a, b):
return (a[1]-b[1])**2+(a[2]-b[2])**2 <= (a[0]-b[0])**2

for _ in range(N):