루미 알고리즘

#1395플래티넘Mafia 2

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.

From last time, the chief of police knows how to interpret these accusations: if police x accuse police y of being honest, this means that either both of them are honest or none of them are. In the same way, if x accuse police y of being corrupt, then exactly one of them must be honest and exactly one of them must be corrupt.

However, it seems that she must have recorded some of the accusations incorrectly. It turns out that the accusations of the policemen are inconsistent with the model of honest and corrupt cops – there is no partition of the cops into honest and corrupt cops such that all the accusations are true.

Determine a set of accusations that is consistent – i.e. there exists a partition of cops into honest and corrupt cops such that all accusations are true – with as large size as possible.

Example

Let there be N = 3 cops, and M = 3 accusations.

Each cop accuses another of being corrupt in a triangle, so that first accuse the second, the second accuse the third, and the third accuse the first.

Since accusing another policeman of being corrupt is equivalent to exactly one of them being corrupt, these three accusations are inconsistent. If we let the first police be honest, the second must be corrupt, so the third one is honest, but not both the first and third police can be honest.

A largest set of accusations that is consistent can be obtained by chosing any two accusations. Say that we keep the accusations of the first and second policemen. Then it is possible that the first and third policemen are indeed honest, and the second is corrupt.

Task

This task is output-only. You will be able to download the input from the judging system, and should submit only your output files to the judge.

Subtasks

The problem will consist of 10 input files. Each file will give between 0 and 10 points.

For a certain test case i, let

  • C_i be the size of the largest set found by a contestant
  • X_i be the size of the set you found

Let the size of the best set found for a certain test case i be B_i, and the size of your set is X_i. Then, your score will be

10 · max{ 0, (X_i - 0.5)/(C_i - 0.5) }

Input format

  • line 1: N M: the number of policemen and the number of accusations, respectively.
  • line 2: A[0] ... A[M - 1]: for each i, A[i] contains the number of the police who made the i:th accusation.
  • line 3: B[0] ... B[M - 1]: for each i, B[i] contains the number of the police was the target of the i:th accusation.
  • line 4: T[0] ... T[M - 1]: for each i, T[i] contains 1 if the i:th accusation was of a policeman's honesty, and 0 if it was of a policeman's corruptness.

Output format

Your output should consist of M integers. The i:th integer should be 0 (if the i:th accusation is not part of your selected set) or 1 (if the i:th accusation is part of your selected set).

예제

예제 1

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

예제 2

입력
3 3
2
0 1 2
1 2 0
0 0 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.