시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
A mafia has infiltrated the city <insert name here>
. This has made the police force of <insert name here>
very confused, with accusations of corruption being made in every direction. The city's $N$ cops (which are numbered between $0$ and $N - 1$) has made a number of accusations about other policemen. Each accusation is either:
An honest cop always tells the truth, while a corrupt cop always lies. In total, there has been $M$ accusations.
The chief of police is now trying to fix the situation, starting with determining how many of her police men are corrupt. She has $G$ different guesses about the number of corrupt cops, and for each such number $C$, she wants to know how many different sets of size $C$ can be corrupt (where all the remaining cops are honest), given that all accusations are consistent.
Let there be $N = 3$ cops, and two accusations. The first cop accused the second cop of being corrupt, and the second cop accused the third cop of being corrupt. There are two cases: either the second cop is corrupt or not.
If the second cop is corrupt, then he lies (so the third cop is honest), and the first cop did not lie (meaning he too is honest).
If the second cop is honest, then the third cop must certainly be corrupt (since the second cop's accusation is now true), and the first cop must be corrupt (since his accusation was a lie).
There are thus two possible subsets of corrupt cops: $\{1, 3\}$ and $\{2\}$, meaning there is one subset of size 1 and one of size 2.
Your task is to compute, for each of the police chief's guesses $C$, in how many ways there can be exactly $C$ corrupt cops. You should implement the functions cops(N, M, A, B, T)
and guess(C)
.
cops(N, M, A, B, T)
- this function will be called exactly once by the judge at the start of the execution.
N
: the number of cops.M
: the number of accusations.A
: an array with $M$ elements. A[i]
($0 \le i < N$) contains the number of the cop who made the $i$:th accusation.B
: an array with $M$ elements. B[i]
($0 \le i < N$) contains the number of the cop who is the target of the $i$:th accusation.T
: an array with $M$ elements. T[i]
($0 \le i < N$) contains 1 or 2 if the $i$:th accusation is of type 1 or 2, respectively.guess(C)
- this function will be called once for every guess.
C
: a number between $0$ and $N$; the guess of the police chief.A code skeleton containing the functions to be implemented, together with a sample grader, can be found at attachments.zip.
The sample judge reads input in the following format:
N M
A[0] ... A[M - 1]
B[0] ... B[M - 1]
T[0] ... T[M - 1]
G
: the number of calls made to guess(C)
.C1 ... CG
: the parameters of the $G$ calls to guess(C)
.The sample judge will write $G$ lines with the return values of guess(C)
.
Let $G$ be the number of calls to guess(C)
.
3 2 1 2 0 1 2 2 4 0 1 2 3
0 1 1 0
Olympiad > Swedish Olympiad in Informatics > 2016 > KATT2 D번
C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)