범인은 너야

각 사람 $i$에 대해 참말쟁이이면 $T_i=1$, 거짓말쟁이이면 $T_i=0$, 범인이면 $C_i=1$, 범인이 아니면 $C_i=0$으로 정의한다. $T_1=1$이다.

각 진술은 두 변수 사이의 XOR 제약 하나로 바꿀 수 있다.

• $t=1$: $T_a\oplus C_b=1$.

변수 $2N$개를 정점으로 하는 그래프에 각 제약을 간선으로 추가한다. 간선의 XOR 값을 관리하는 가중치 있는 Disjoint Set Union을 사용하면, 제약이 모순되는지 판정할 수 있다. 모순이 하나라도 있으면 가능한 상태가 없으므로 -1을 출력한다.

모순이 없다면 각 연결 요소의 변수값을 전체적으로 뒤집어도 제약은 유지된다. 단, $T_1$이 있는 연결 요소는 $T_1=1$로 고정된다. 따라서 $C_i$가 과 같은 연결 요소에 있고 인 경우에만 번 사람이 모든 가능한 상태에서 범인이다. 번호 순서대로 이를 확인한다.

시간 복잡도는 $O((N+M)\alpha(N))$, 공간 복잡도는 $O(N)$이다.

Solution written by GPT6