I - XOR Reachable
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
整数 N,M,K と N 頂点 M 辺の無向グラフが与えられます。グラフの頂点には 1 から N の番号が、辺には 1 から M の番号が付けられています。辺 i (1 ≤ i ≤ M) は頂点 A_i と頂点 B_i の間をつないでいて、辺上には非負整数 C_i が置かれています。
Q 個のクエリが与えられます。i 番目 (1 ≤ i ≤ Q) のクエリでは、整数 D_{i} が与えられるので、次の条件を全て満たす整数の組 (u,v) の個数を求めてください。
- 1\le u\lt v\le N
- (C_{j} \oplus D_{i})\lt K を満たすような辺 j のみを通って、頂点 u から頂点 v まで移動することが可能
ただし \oplus はビット単位 \text{XOR} 演算を表します。
ビット単位 \text{XOR} 演算とは
非負整数 X,Y のビット単位 \text{XOR} 演算、 X\oplus Y は以下のように定義されます。- X\oplus Y を二進表記したときの 2^{k}の位 (0\le k) は、 A,B を二進表記したときの 2^{k} の位が異なるなら 1 、そうでないなら 0 とする。
制約
- 入力は全て整数
- 2\le N\le 10^{5}
- 1\le M\le 10^{5}
- 0\le K\lt 2^{30}
- 1\le A_{i} \lt B_{i}\le N (1 ≤ i ≤ M)
- 0\le C_{i}\lt 2^{30} (1 ≤ i ≤ M)
- 1\le Q\le 10^{5}
- 0\le D_{i}\lt 2^{30} (1 ≤ i ≤ Q)
入力
入力は以下の形式で標準入力から与えられる。
N M K A_{1} B_{1} C_{1} A_{2} B_{2} C_{2} \vdots A_{M} B_{M} C_{M} Q D_{1} D_{2} \vdots D_{Q}
出力
Q 行出力せよ。 i 行目 (1\le i\le Q) には i 番目のクエリの答えを出力せよ。
入力例 1
4 5 5 1 2 17 1 3 4 2 3 20 2 4 3 3 4 5 4 0 7 16 167
出力例 1
2 6 3 0
- 1 番目のクエリでは、辺 2,4 のみを通ることができます。
- 2 番目のクエリでは、辺 2,4,5 のみを通ることができます。
- 3 番目のクエリでは、辺 1,3 のみを通ることができます。
- 4 番目のクエリでは、どの辺も通ることができません。
入力例 2
9 13 488888932 2 7 771479959 3 8 783850182 5 7 430673756 6 8 350738034 4 9 400768807 2 3 83653266 1 2 829786563 5 8 357613791 7 9 579696618 3 7 423191200 3 5 867380255 1 9 907715012 6 9 1033650694 8 498260055 144262908 117665696 848664012 983408133 32610599 478007408 134182829
出力例 2
16 7 5 13 13 16 16 5