問題一覧 > ネタ問題

No.8113 How Many Liars Are There?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : 👑 獅子座じゃない人獅子座じゃない人 / テスター : 👑 seekworserseekworser
0 ProblemId : 10782 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-01 22:10:08

問題文

2N2N 人の人がいて、順に人 i (1i2N)i\ (1\leq i\leq 2N) とします。
ii は、それぞれ正直者と嘘つきのどちらかです。

i (1iN)i\ (1\leq i\leq N) は、それぞれ人 Pi (1PiN, iPi)P_i\ (1\leq P_i\leq N,\ i\neq P_i) が正直者か嘘つきかどうかを言います。
ii が正直者の場合、人 PiP_i が正直者であれば「人 PiP_i は正直者である」と言い、人 PiP_i が嘘つきであれば「人 PiP_i は嘘つきである」と言います。
一方、人 ii が嘘つきの場合、人 PiP_i が正直者であれば「人 PiP_i は嘘つきである」と言い、人 PiP_i が嘘つきであれば「人 PiP_i は正直者である」と言います。

また、人 (i+N) (1iN)(i+N)\ (1\leq i\leq N) は、それぞれ人 ii の発言の内容を言います。
(i+N)(i+N) が正直者の場合、人 ii が「人 PiP_i は正直者である」と言えば「人 ii は『人 PiP_i は正直者である』と言った」と言い、人 ii が「人 PiP_i は嘘つきである」と言えば「人 ii は『人 PiP_i は嘘つきである』と言った」と言います。
一方、人 (i+N)(i+N) が嘘つきの場合、人 ii が「人 PiP_i は正直者である」と言えば「人 ii は『人 PiP_i は嘘つきである』と言った」と言い、人 ii が「人 PiP_i は嘘つきである」と言えば「人 ii は『人 PiP_i は正直者である』と言った」と言います。

以下の条件をともに満たすように、それぞれの人 i (1i2N)i\ (\boldsymbol{1}\leq i\leq \boldsymbol{2N}) に正直者であるか嘘つきであるかを割り当てられるならばYesを、どのように割り当てても条件(の少なくとも片方)を満たさないならばNoを出力してください。

  • 与えられる Ai (1iN)A_i\ (1\leq i\leq N) について、 Ai=0A_i=0 ならば人 (i+N)(i+N) が「人 ii は『人 PiP_i は正直者である』と言った」と言うように、 Ai=1A_i=1 ならば人 (i+N)(i+N) が「人 ii は『人 PiP_i は嘘つきである』と言った」と言うように割り当てられている。
  • 与えられる KK について、人 i (1i2N)i\ (\boldsymbol{1}\leq i\leq \boldsymbol{2N}) のなかに嘘つきはちょうど KK 人いる。

入力

N KN\ K
P1 P2 P3  PNP_1\ P_2\ P_3\ \ldots\ P_N
A1 A2 A3  ANA_1\ A_2\ A_3\ \ldots\ A_N

  • 入力は全て整数
  • 2N10002\leq N\leq 1000
  • 0K2N0\leq K\leq 2N
  • 1PiN (1iN)1\leq P_i\leq N\ (1\leq i\leq N)
  • iPi (1iN)i\neq P_i\ (1\leq i\leq N)
  • Ai{0,1} (1iN)A_i\in\{0,1\}\ (1\leq i\leq N)

出力

条件を満たすように正直者であるか嘘つきであるかを割り当てられるならばYesを、割り当てられないならばNoを出力し、最後に改行してください。

サンプル

サンプル1
入力
3 5
2 3 1
0 0 1
出力
Yes

1,3,4,5,61,3,4,5,6 が嘘つきである場合を考えます。
11 は「人 22 は嘘つきである」と言い、人 22 は「人 33 は嘘つきである」と言い、人 33 は「人 11 は正直者である」と言います。
したがって、人 44 は「人 11 は『人 22 は正直者である』と言った」と言い、人 55 は「人 22 は『人 33 は正直者である』と言った」と言い、人 66 は「人 33 は『人 11 は嘘つきである』と言った」と言います。
これは条件を満たす割り当て方となっているため、Yesを出力します。

0K2N0\leq K\leq 2N に注意してください。

サンプル2
入力
2 0
2 1
0 1
出力
No

全ての人が正直者である場合、 A1=0, A2=1A_1=0,\ A_2=1 の条件を満たすことはありません。

サンプル3
入力
10 16
2 3 1 5 4 7 8 6 6 8
0 1 0 1 0 1 0 1 0 1
出力
Yes

サンプル4
入力
10 17
2 3 1 5 4 7 8 6 6 8
0 1 0 1 0 1 0 1 0 1
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。