← 返回题目列表

AtCoder · joi2022_yo2_e

E. 贸易计划

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

配点: 100 点

問題文

JOI美国 编号至 1 减去 N 编号最多为 N 城市和1 减去 M 编号最多为 M 有一条真正的路。路 i (1 \leqq i \leqq M) 是一座城市 U_i 和城市 如下选择 V_i 双向连接。

JOI美国 它由 1 减去 K 编号最多为 K 状态组成。城市 j (1 \leqq j \leqq N) 是状态 它属于 S_j 。此外,每个州至少有 1 包含 1 个城市。

JOI主席K,即美国工业部长,将 我想进行 Q 交易。k 第笔交易 (1 \leqq k \leqq Q) 是一座城市 A_k 来自城市 B_k 通过多条道路和城市运输特色产品。然而,只有各州与这种贸易合作。 S_{A_k} 并状态 仅 S_{B_k} ( 说明如果S_{A_k} = S_{B_k} 仅 S_{A_k} ),如果经过不属于这些州的城市,特殊产品将会被盗。

K主席想知道是否有一条可以进行贸易的运输路线,以防止特产被盗。给定城市和道路、州和贸易信息的位置,编写一个程序来确定是否可以安全地为每个贸易交付特种产品。

制約

  • 2 \leqq N \leqq 400\,000.
  • 1 \leqq M \leqq 400\,000.
  • 1 \leqq K \leqq N.
  • 1 \leqq U_i < V_i \leqq N (1 \leqq i \leqq M).
  • (U_i, V_i) \neq (U_j, V_j) (1 \leqq i < j \leqq M).
  • 1 \leqq S_j \leqq K (1 \leqq j \leqq N).
  • 全部 l (1 \leqq l \leqq K),S_j = l 变为 j (1 \leqq j \leqq N) 存在。
  • 1 \leqq Q \leqq 400\,000.
  • 1 \leqq A_k \leqq N (1 \leqq k \leqq Q).
  • 1 \leqq B_k \leqq N (1 \leqq k \leqq Q).
  • A_k \neq B_k (1 \leqq k \leqq Q).
  • 所有输入值都是整数。 属于

小課題

  1. (5 点) N \leqq 1\,000,M \leqq 1\,000,Q \leqq 1\,000.
  2. (11 点) 州 l (1 \leqq l \leqq K的所有城市都有道路和州 你们只能通过属于 l 的城市相互旅行。
  3. (42 点) N \leqq 80\,000,M \leqq 80\,000,Q \leqq 80\,000.
  4. (42 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为对于该子作业是正确的。

每次提交的分数是所提交源代码被认为正确的子任务分数的总和。

该作业的分数是该作业所有提交的最高分数。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

N M K
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S_1 S_2 \cdots S_N
Q
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

出力

到标准输出 Q 行。k 行目 (1 \leqq k \leqq Q)有k 是否可以交付贸易中的特殊产品 1 ,如果不可能 输出 0 。 第


入力例 1

4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

出力例 1

1
0
1
  • 1 笔交易是 1 或状态 仅通过属于 2 的城市, 目的是将特色产品运输到 1 来自城市 2 。城市 1 → 都市 2 满足条件,所以 目的是将特色产品运输到1 。 在
  • 2 笔交易是 1 的城市, 目的是将特色产品运输到 1 来自城市 3 。由于没有满足条件的运输路线,0 。 在
  • 3 笔交易是 1 或状态 仅通过属于 2 的城市, 目的是将特色产品运输到 1 来自城市 4 。城市 1 → 都市 2 → 都市 3 → 都市 4 满足条件,所以 目的是将特色产品运输到1 。 在

此输入示例是一个小作业。 1, 3, 4 满足约束。


入力例 2

4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

出力例 2

0
1
0
1

此输入示例是一个小作业。 1, 3, 4 满足约束。


入力例 3

6 5 3
1 2
3 4
5 6
1 4
3 5
1 1 2 2 3 3
4
1 4
1 5
3 6
4 3

出力例 3

1
0
1
1

此输入示例满足所有子任务约束。


入力例 4

8 11 3
4 8
1 8
4 6
3 5
2 4
7 8
6 7
3 4
1 4
2 3
3 8
2 3 1 1 2 1 2 1
10
8 2
8 1
2 7
5 3
5 7
4 8
1 8
6 8
6 5
1 8

出力例 4

1
1
0
1
0
1
1
1
1
1

此输入示例是一个小作业。 1, 3, 4 满足约束。