[GCJ 2022 Finals] Goose, Goose, Ducks?

题目描述

The first international Geese conference just wrapped up, and even though it should have been a happy occasion, it was bittersweet. The organizers found a paper with detailed plans of a duck infiltration. Now, they are trying to identify the infiltrating group from among the attendees.

The document that they found contained a list of $\mathbf{M}$ triples of integers $(\mathbf{X}_i, \mathbf{Y}_i, \mathbf{C}_i)$ meaning the ducks would meet exactly $\mathbf{C}_i$ seconds after the start of the conference at point $(\mathbf{X}_i, \mathbf{Y}_i)$, which is $\mathbf{X}_i$ meters east and $\mathbf{Y}_i$ meters north of the center of the conference floor. Each goose may or may not have been at those specific points at those specific times, but every duck certainly was.

Both ducks and geese walk at a maximum speed of one meter per second, which means an attendee that is at point $(x, y)$ at time $t$ can reach any point of the form $(x + \Delta_x, y + \Delta_y)$ by time $t + \Delta_t$ as long as $\Delta_x^2 + \Delta_y^2 \leq \Delta_t^2$. Each attendee's position at time 0 can be any point, independently of the other attendees.

After the discovery, the group held a questioning session to try to identify the ducks. During that session, attendees issued a series of statements, one at a time. The $j$-th of those, in the order they were issued, was made by attendee $\mathbf{A}_j$, claiming that both they and attendee $\mathbf{B}_j$ were at point $(\mathbf{U}_j, \mathbf{V}_j)$ exactly $\mathbf{D}_j$ seconds after the start of the conference. Points in statements may or may not be points where duck meetings happened.

Statements from geese are always true, but ducks may lie. Moreover, ducks know which attendees are ducks and which are geese. To avoid getting caught easily, ducks only make statements that are consistent with all statements previously made by geese. Note that statements made by geese are consistent with all ducks being at all duck meetings.

It may not be possible to determine all the ducks with the information provided. However, knowing the minimum number of ducks will at least provide a lower bound on the level of duck activity. Note that there was at least one duck. Find this minimum number of ducks.

Formally, a hypothesis $H$ is a partition of all attendees into a set of ducks (named $H$-ducks) and geese (named $H$-geese). $H$ is consistent with a set of statements $S$ if there exists a path for each attendee moving at most one meter per second such that:

• all $H$-ducks were at all duck meetings and
• for each statement in $S$ claiming that $A$ saw $B$ at point $P$ at time $T$, both $A$ and $B$'s paths went through point $P$ at time $T$.

A hypothesis $H$ is feasible under a set of statements $S$ if:

• $H$-ducks is not empty (i.e., there was at least one duck),
• the subset of all statements from $S$ made by members of $H$-geese is consistent with $H$ (i.e., statements from geese are always true), and
• for each statement $s \in S$ made by a member of $H$-ducks, if $P \subseteq S$ is the subset of statements made by members of $H$-geese issued before $s$, there exists a hypothesis $H'$ (which may or may not be equal to $H$) such that $\{s\} \cup P$ is consistent with $H'$ (i.e., ducks do not contradict previous statements made by geese).

Notice that the hypotheses $H$ such that $H$-ducks contains all attendees is always feasible.

Find the minimum size of $H$-ducks over all feasible hypotheses $H$.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case starts with a line containing three integers, $\mathbf{N}$, $\mathbf{M}$, and $\mathbf{S}$, representing the numbers of attendees, duck meetings, and statements, respectively. The next $\mathbf{M}$ lines each describe a different duck meeting with three integers $\mathbf{X}_i$, $\mathbf{Y}_i$, and $\mathbf{C}_i$, representing that there was a meeting at point $(\mathbf{X}_i, \mathbf{Y}_i)$, held exactly $\mathbf{C}_i$ seconds after the start of the conference. Then, the last $\mathbf{S}$ lines of a test case each describe a statement. The $j$-th of these lines describes the $j$-th issued statement with five integers $\mathbf{A}_j$, $\mathbf{B}_j$, $\mathbf{U}_j$, $\mathbf{V}_j$, and $\mathbf{D}_j$, representing that attendee $\mathbf{A}_j$ stated that they and attendee $\mathbf{B}_j$ were both at point $(\mathbf{U}_j, \mathbf{V}_j)$ exactly $\mathbf{D}_j$ seconds after the start of the conference.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of ducks that might have infiltrated the conference.

输入输出样例

输入样例 #1

2
2 1 2
1 2 3
1 2 1 1 1
2 1 2 2 2
4 2 4
4 3 10
-4 -3 20
1 3 4 3 11
2 4 0 0 16
3 1 6 3 9
4 2 0 0 16

输出样例 #1

Case #1: 1
Case #2: 2

说明/提示

Sample Explanation

In Sample Case #1, attendee 1 being the only duck is a feasible hypothesis.

In Sample Case #2, attendees 2 and 4 being the only ducks is a feasible hypothesis. Note that there is at least one duck, so all attendees being geese is not feasible.

Limits

• $1 \leq \mathbf{T} \leq 50$.
• $-10^9 \leq \mathbf{X}_i \leq 10^9$, for all $i$.
• $-10^9 \leq \mathbf{Y}_i \leq 10^9$, for all $i$.
• $1 \leq \mathbf{C}_i \leq 10^9$, for all $i$.
• $\mathbf{C}_i < \mathbf{C}_{i+1}$, for all $i$.
• $(\mathbf{X}_i - \mathbf{X}_{i+1})^2 + (\mathbf{Y}_i - \mathbf{Y}_{i+1})^2 \leq (\mathbf{C}_i - \mathbf{C}_{i+1})^2$, for all $i$.
• $1 \leq \mathbf{A}_j \leq \mathbf{N}$, for all $j$.
• $1 \leq \mathbf{B}_j \leq \mathbf{N}$, for all $j$.
• $\mathbf{A}_j \neq \mathbf{B}_j$, for all $j$.
• $-10^9 \leq \mathbf{U}_j \leq 10^9$, for all $j$.
• $-10^9 \leq \mathbf{V}_j \leq 10^9$, for all $j$.
• $1 \leq \mathbf{D}_j \leq 10^9$, for all $j$.
• $(\mathbf{A}_j, \mathbf{B}_j, \mathbf{U}_j, \mathbf{V}_j, \mathbf{D}_j) \neq (\mathbf{A}_k, \mathbf{B}_k, \mathbf{U}_k, \mathbf{V}_k, \mathbf{D}_k)$, for all $j \neq k$.

Test Set 1 (11 Pts, Visible Verdict)

• Time limit: 20 seconds.
• $2 \leq \mathbf{N} \leq 50$.
• $1 \leq \mathbf{M} \leq 50$.
• $1 \leq \mathbf{S} \leq 50$.

Test Set 2 (24 Pts, Hidden Verdict)

• Time limit: 60 seconds.
• $2 \leq \mathbf{N} \leq 10^5$.
• $1 \leq \mathbf{M} \leq 10^5$.
• $1 \leq \mathbf{S} \leq 10^5$.