問題一覧 > 通常問題

No.1421 国勢調査 (Hard)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 43
作問者 : 57tggx57tggx / テスター : logxlogx
0 ProblemId : 5848 / 出題時の順位表
問題文最終更新日: 2021-01-31 09:44:47

問題文

ある王国には $N$ 個の町があり,それぞれには $1$ から $N$ までの番号が付いている.番号 $i$ ( $i = 1, 2, \ldots, N$ )の町には $X_i$ 軒の家が建っていて,今 $0 \leq X_i < 2^{30}$ であることだけがわかっている. この国の王は,どの町に家が何軒あるのか知りたいと思っている.

あるとき $M$ 人の旅人がこの国を訪れた. $j$ ( $j = 1, 2, \ldots, M$ )番目の旅人は,王国内の町のうち $A_j$ 個を回り,その番号は $B_{j1}, B_{j2}, \ldots, B_{jA_j}$ であった.各旅人 $j$ は,王国を去るとき王に次の 2 つを報告した.

  • 自分の回った町の数 $A_j$ と,その番号 $B_{j1}, B_{j2}, \ldots, B_{jA_j}$ .
  • 自分の回った $A_j$ 個の町について,家の軒数の総 XOR をとった値 $Y_j$ .すなわち$$Y_j = X_{B_{j1}} \oplus X_{B_{j2}} \oplus \cdots \oplus X_{B_{jA_j}}$$

王は, $M$ 人の旅人の報告をもとに各町の家の軒数 $X_1, X_2, \ldots, X_N$ を割り出すことにした.

しかし,旅人の中には虚偽の報告をした者がいる可能性もある.

$M$ 人の旅人の報告全てと合致するような $X_1, X_2, \ldots, X_N$ の値の組が存在するならば,そのうちの一つを出力せよ.そうでないとき(旅人の報告に矛盾があるとき), $-1$ を出力せよ.

入力

$N$ $M$
$A_1$
$B_{11}$ $B_{12}$ $\ldots$ $B_{1A_1}$
$Y_1$
$A_2$
$B_{21}$ $B_{22}$ $\ldots$ $B_{2A_2}$
$Y_2$
$\vdots$
$A_M$
$B_{M1}$ $B_{M2}$ $\ldots$ $B_{MA_M}$
$Y_M$

制約:

  • 入力は全て整数である.
  • $1 \leq N \leq 50$
  • $1 \leq M \leq 10^4$
  • 各 $j = 1, 2, \ldots, M$ について:
    • $1 \leq A_j \leq N$
    • $1 \leq B_{j1} < B_{j2} < \cdots < B_{jA_j} \leq N$
    • $0 \leq Y_i < 2^{30}$

出力

矛盾がなければ,改行区切りで

$X_1$
$X_2$
$\vdots$
$X_N$
を出力せよ.ただし,全ての $i = 1, 2, \ldots, N$ について $0 \leq X_i < 2^{30}$ が成り立っていなければならない.また,複数ある場合はどれを出力してもよい.

矛盾があれば,

-1
と出力せよ.

サンプル

サンプル1
入力
3 3
2
1 2
3
2
2 3
5
1
3
4
出力
2
1
4

町 $1$ , $2$ , $3$ にはそれぞれ家が $2$ , $1$ , $4$ 軒建っている.

旅人 $1$ は町 $1$ , $2$ を訪れ,総 XOR は $3$ だった.

旅人 $2$ は町 $2$ , $3$ を訪れ,総 XOR は $5$ だった.

旅人 $3$ は町 $3$ を訪れ,総 XOR は $4$ だった.

サンプル2
入力
2 3
1
1
5
1
2
5
2
1 2
5
出力
-1

旅人 $1$ , $2$ の情報に基づくと町 $1$ , $2$ にある家はともに $5$ 軒となるが,これは旅人 $3$ の情報と矛盾する.

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