루미 알고리즘

#1394다이아Mafia

PO 2016 훈련 캠프코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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.

Example

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.

Task

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 ≤ i < N) contains the number of the cop who made the i:th accusation.
  • B: an array with M elements. B[i] (0 ≤ 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 ≤ 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 http://progolymp.se/uploads/kattis-attachments/mafia.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Let G be the number of calls to guess(C).

SubtaskPointsLimits
111N ≤ 20, M ≤ 30, G ≤ 2000.
213N ≤ 2000, M ≤ 70000, G ≤ 2000. There are only two possible sets of corrupt cops.
322N ≤ 2000, M ≤ 70000, G ≤ 1.
421N ≤ 100, M ≤ 10000, G ≤ 200.
533N ≤ 2000, M ≤ 70000, G ≤ 2000.

Input format

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).

Output format

The sample judge will write G lines with the return values of guess(C).

예제

예제 1

입력
3 2
1 2
0 1
2 2
4
0 1 2 3
출력
0 1 1 0

출처 표기

출처: Programmeringsolympiaden 2016년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.