← 返回题目列表

AtCoder · ttpc2022_i

I. 异或可达

中文机器翻译题面 查看原题

配点 : 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 。
例如, 3\oplus 5=6 。 (用二进制表示法, 输出 011\oplus 101=110 )

制約

  • 所有输入均为整数
  • 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