← 返回题目列表

AtCoder · joi2024ho_e

E. 路网维护2(Road Service 2)

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

配点: 100 点

問題文

JOI城有无限长 H 东西向道路及 W 有南北向道路组成的网格状路网。从北方 i 本目 (1 \leqq i \leqq H) 东西向道路和从西边 j 本目 (1 \leqq j \leqq W) 南北道路交叉的交叉路口是交叉路口。 我们称之为 (i, j) 。

目前,部分道路因维护不善而封闭。具体封路情况如下。

  • 从北方 i 本目 (1 \leqq i \leqq H) 东西路交叉口 (i, j) 和交叉路口 连接 (i, j + 1) 的部分(1 \leqq j \leqq W - 1) 表示A_{i, j} = 0 当道路封闭时, 当A_{i, j} = 1 时还可以。
  • 从西边 j 本目 (1 \leqq j \leqq W) 南北路交叉口 (i, j) 和交叉路口 连接 (i + 1, j) 的部分(1 \leqq i \leqq H - 1) 表示B_{i, j} = 0 当道路封闭时, 当B_{i, j} = 1 时还可以。
  • 道路的其他部分,即 H \times W 十字路口以外的所有区域均禁止通行。

担任JOI市市长的K主席表示,道路网络 我决定创建整備計画。维护计划是0 次或更多 它由整備组成。 1 维护期间,1 \leqq i \leqq H 的整数 i 在 1 选择一项并执行以下操作: 满足

1 \leqq j \leqq W - 1 满足全部 关于整数 j ,来自北方 i 东西主干道交叉口 使连接 (i, j) 和交叉路口 连接 (i, j + 1) 的部分能够通过(如果它是关闭的)。这包括整个 需要 C_i 天。然而,C_i 是 1 或 2 。

维护计划中包含的多项维护不能同时并行执行。因此,执行维护计划所需的天数是维护计划中包含的所有维护所需的总天数。

K主席首先会要求你在重要的城市设施之间移动。 我问了 Q 问题。 问题 k 個目 (1 \leqq k \leqq Q)如下。

T_k 交叉路口 (X_{k, 1}, Y_{k, 1}), (X_{k, 2}, Y_{k, 2}), \dots, (X_{k, T_k}, Y_{k, T_k}) 是否有一项发展计划允许人们仅使用可通行的路段在两个地区之间出行? 如果是这样,实施这样的维护计划所需的最少天数是多少?

考虑到道路封闭情况、开发每条东西向道路所需的天数以及 K 主席的问题内容,​​创建一个程序来回答 K 主席的所有问题。


入力

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

H W Q 
A_{1,1}A_{1,2}\cdots A_{1,W - 1} 
A_{2,1}A_{2,2}\cdots A_{2,W - 1} 
\vdots 
A_{H,1}A_{H,2}\cdots A_{H,W - 1} 
B_{1,1}B_{1,2}\cdots B_{1,W} 
B_{2,1}B_{2,2}\cdots B_{2,W} 
\vdots 
B_{H - 1,1}B_{H - 1,2}\cdots B_{H - 1,W} 
C_1 C_2 \cdots C_H 
\mathrm{Query}_1 
\mathrm{Query}_2 
\vdots 
\mathrm{Query}_Q

然而,每个 \mathrm{Query}_k (1 \leqq k \leqq Q) 具有以下格式。 在

T_k 
X_{k,1} Y_{k,1} 
X_{k,2} Y_{k,2} 
\vdots 
X_{k,T_k} Y_{k,T_k}

出力

到标准输出 输出 Q 行。 在k 行目 (1 \leqq k \leqq Q)有 打印第T_k 交叉路口 (X_{k, 1}, Y_{k, 1}), (X_{k, 2}, Y_{k, 2}), \dots, (X_{k, T_k}, Y_{k, T_k}) 之间, 如果存在仅允许通过道路可通行部分的维护计划,请打印执行该计划所需的最少天数;否则, 输出 -1 。


制約

  • 2 \leqq H.
  • 2 \leqq W.
  • H \times W \leqq 1\,000\,000.
  • 1 \leqq Q \leqq 100\,000.
  • A_{i, j} 是 0 或 1 (1 \leqq i \leqq H, 1 \leqq j \leqq W - 1).
  • B_{i, j} 是 0 或 1 (1 \leqq i \leqq H - 1, 1 \leqq j \leqq W).
  • C_i 是 1 或 2 (1 \leqq i \leqq H).
  • 2 \leqq T_k (1 \leqq k \leqq Q).
  • T_1 + T_2 + \cdots + T_Q \leqq 200\,000.
  • 1 \leqq X_{k, l} \leqq H (1 \leqq k \leqq Q, 1 \leqq l \leqq T_k).
  • 1 \leqq Y_{k, l} \leqq W (1 \leqq k \leqq Q, 1 \leqq l \leqq T_k).
  • (X_{k, 1}, Y_{k, 1}), (X_{k, 2}, Y_{k, 2}), \dots, (X_{k, T_k}, Y_{k, T_k}) 不同(1 \leqq k \leqq Q).
  • 所有输入值均为整数。

小課題

  1. (10 点) C_i = 1 (1 \leqq i \leqq H),Q \leqq 5,T_k = 2 (1 \leqq k \leqq Q),A_{i, j} = 0 (1 \leqq i \leqq H, 1 \leqq j \leqq W - 1).
  2. (6 点) C_i = 1 (1 \leqq i \leqq H),Q \leqq 5,T_k = 2 (1 \leqq k \leqq Q).
  3. (15 点) C_i = 1 (1 \leqq i \leqq H),Q \leqq 5.
  4. (11 点) C_i = 1 (1 \leqq i \leqq H),T_k = 2 (1 \leqq k \leqq Q).
  5. (6 点) C_i = 1 (1 \leqq i \leqq H).
  6. (12 点) Q \leqq 5.
  7. (26 点) T_k = 2 (1 \leqq k \leqq Q).
  8. (14 点)没有额外的限制。

入力例 1

4 3 4
00
00
00
00
100
001
000
1 1 1 1
2
1 1
3 3
2
3 1
1 2
2
2 3
3 3
2
4 2
3 2

出力例 1

1
3
0
-1

下图为目前封路情况。灰色表示道路封闭,蓝色表示道路开放。 在第

  • 1 题中,整数 如果进行维护选择 i 作为 转到 2 ,则封路情况如下图所示,路口将被封闭。 您现在可以在 (1, 1), (3, 3) 之间来回移动。

    这个 1 执行仅包含一次维护的维护计划所需的天数为 1 ,并且交叉口可以在比这更少的时间内完成。 (1, 1), (3, 3) 没有允许两者之间访问的维护计划。1 。
  • 2 题中,整数 如果进行维护选择 i 分别 就像选择 1, 2, 3 喜欢选择 3 如果进行两次维护,交叉口 您现在可以在 (3, 1), (1, 2) 之间来回移动。 这个 3 执行包含维护的维护计划所需的天数为 3 ,并且交叉口可以在比这更少的时间内完成。 (3, 1), (1, 2) 没有允许两者之间访问的维护计划。3 。
  • 3 第二个问题是关于维护的。 1 交叉口无需做两次 您可以在 (2, 3), (3, 3) 之间来回切换,所以0 。
  • 4 第二题中,交集 (4, 2), (3, 2) 没有允许两者之间访问的维护计划。-1 。

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


入力例 2

4 4 4
100
110
011
010
0010
1001
0101
1 1 1 1
2
1 2
3 1
2
1 4
4 1
2
3 2
1 2
2
4 3
1 1

出力例 2

1
3
2
2

此输入示例是一个小作业。 2, 3, 4, 5, 6, 7, 8 满足约束。


入力例 3

7 3 3
10
00
00
10
00
01
00
110
101
011
001
110
100
1 1 1 1 1 1 1
3
7 2
3 1
3 2
3
3 1
6 3
2 3
7
2 2
1 3
7 3
5 2
1 2
7 2
3 1

出力例 3

3
2
4

此输入示例是一个小作业。 3, 5, 6, 8 满足约束。


入力例 4

4 3 3
00
00
10
00
110
011
001
1 2 2 2
2
1 1
3 1
2
4 3
2 1
2
4 1
1 3

出力例 4

1
2
5

此输入示例是一个小作业。 6, 7, 8 满足约束。


入力例 5

7 3 2
01
00
00
00
00
10
01
100
110
011
001
101
001
1 1 2 1 1 2 2
3
7 2
1 3
5 1
5
1 1
2 2
3 1
2 3
4 2

出力例 5

4
1

此输入示例是一个小作业。 6, 8 满足约束。