시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.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:

  1. Police number $i$ is an honest cop.
  2. Police number $i$ is a corrupt cop.

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.
    • The function has no return value.
  • guess(C) - this function will be called once for every guess.
    • C: a number between $0$ and $N$; the guess of the police chief.
    • The return value of the function will never exceed $10^{18}$.
    • The function should return the number of possible sets of corrupt cops of size $C$, where the remaining cops are honest.

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:

  • line $1$: N M
  • line $2$: A[0] ... A[M - 1]
  • line $3$: B[0] ... B[M - 1]
  • line $4$: T[0] ... T[M - 1]
  • line $5$: G: the number of calls made to guess(C).
  • line $6$ 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).

  • $N \le 2\,000$
  • $M \le 70\,000$
  • $G \le 2\,000$

예제 입력 1

3 2
1 2
0 1
2 2
4
0 1 2 3

예제 출력 1

0 1 1 0

출처

Olympiad > Swedish Olympiad in Informatics > 2016 > KATT2 D번

  • 문제를 만든 사람: Johan Sannemo

제출할 수 있는 언어

C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.