[JOI 2024 Final] 路网服务 2 / Road Service 2

Luogu

IDLGP10209

Time3000ms

Memory1024MB

DifficultyP7

贪心倍增2024JOI（日本）

JOI 市有一个由 $H$ 条东西向的无限长道路和 $W$ 条南北向的道路组成的网格状道路网。从北边数第 $i\ (1 \leq i \leq H)$ 条的东西向的道路和从西边数第 $j\ (1 \leq j \leq W)$ 条的南北向的道路相交的地方称作交叉点 $(i, j)$。现在，由于道路年久失修，一部分道路被封锁了。具体的封锁情况如下： - 如果 $A_{i, j}=0\ (1 \leq i \leq H,1 \leq j \leq W-1)$，则从北边数第 $i$ 条的东西向的道路的，交叉点 $(i, j)$ 和交叉点 $(i, j+1)$ 之间的部分就是封锁的；如果 $A_{i, j}=1$ 则是可以通行的。 - 如果 $B_{i, j}=0\ (1 \leq j \leq W,1 \leq i \leq H-1)$ 从西边数第 $j$ 条的南北向的道路的，交叉点 $(i, j)$ 和交叉点 $(i+1, j)$ 之间的部分就是封锁的；如果 $B_{i, j}=1$ 就是可以通行的。 - 道路的其他部分，即 $H \times W$ 个交叉点外面的部分都是封锁的。 JOI 市的市长 K 理事长决定制定一个道路维修计划。维修计划由大于等于 $0$ 次维修构成。一次维修时选择一个满足的整数 $i\ (1 \leq i \leq H)$，然后进行以下的操作：对于**所有**满足 $1 \leq j \leq W-1$ 的整数 $j$，如果从北边数第 $i$ 条的东西向的道路的，交叉点 $(i, j)$ 和交叉点 $(i, j+1)$ 之间的部分是封锁的话，将其变成可以通行的。这个过程总共需要 $C_{i}$ 天。其中，$C_{i}$ 为 $1$ 或 $2$。维修计划里包含的多次维修不能同时进行。因此，维修计划的执行所需要的天数是维修计划里包含的所有维修所需要的天数的总和。为了让市里的重要设施之间能够互相通行，K 理事长向你提出了 $Q$ 个问题。第 $k\ (1 \leq k \leq Q)$ 个问题是这样的：是否存在一个维修计划，能够让 $T_{k}$ 个交叉点 $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ 之间，只通过可以通行的道路互相通行。如果存在的话，执行这样的维修计划最少需要多少天。给定道路网的封锁情况，各条道路的维修所需要的天数，K 理事长的问题的内容，编写一个程序来回答 K 理事长的所有问题。 ## Input 第一行包含三个整数 $H,W,Q$。接下来 $H$ 行，每行包含一个长度为 $W-1$ 的字符串，表示 $A_{i,1},A_{i,2},\ldots ,A_{i,W-1}$。接下来 $H-1$ 行，每行包含一个长度为 $W$ 的字符串，表示 $B_{i,1},B_{i,2},\ldots ,B_{i,W}$。接下来一行包含 $H$ 个用空格分隔的整数 $C_1,C_2,\ldots ,C_H$。接下来有 $Q$ 个询问，每个询问用以下形式给出：第一行包含一个整数 $T_k$。接下来 $T_k$ 行每行包含两个整数 $X_{k,i},Y_{k,i}$。 ## Output 输出 $Q$ 行，第 $k$ 行 $(1 \leq k \leq Q)$ 里，如果存在一个维修计划，能够让 $T_{k}$ 个交叉点 $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ 之间互相通行，就输出执行这样的维修计划最少需要多少天。否则输出 $-1$。 [samples] ## Note 对于所有输入数据，满足： - $2 \leq H$ - $2 \leq W$ - $H \times W \leq 10^6$ - $1 \leq Q \leq 10^5$ - $A_{i, j}$ 为 $0$ 或 $1\ (1 \leq i \leq H, 1 \leq j \leq W-1)$ - $B_{i, j}$ 为 $0$ 或 $1\ (1 \leq i \leq H-1,1 \leq j \leq W)$ - $C_{i}$ 为 $1$ 或 $2\ (1 \leq i \leq H)$ - $2 \leq T_{k}\ (1 \leq k \leq Q)$ - $T_{1}+T_{2}+\cdots+T_{Q} \leq 2\times 10^5$ - $1 \leq X_{k, l} \leq H\ (1 \leq k \leq Q, 1 \leq l \leq T_{k})$ - $1 \leq Y_{k, l} \leq W\ (1 \leq k \leq Q, 1 \leq l \leq T_{k})$ - $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots,(X_{k, T_{k}}, Y_{k, T_{k}})$ 各不相同 $(1 \leq k \leq Q)$ 详细子任务附加限制及分值如下表所示。 |子任务| 附加限制| 分值| | :-: | :-: | :-:| |1| $C_{i}=1\ (1 \leq i \leq H), Q \leq 5, T_{k}=2\ (1 \leq k \leq Q), A_{i, j}=0\ (1 \leq i \leq H, 1 \leq j \leq W-1)$| $10$| |2|$ C_{i}=1\ (1 \leq i \leq H), Q \leq 5, T_{k}=2\ (1 \leq k \leq Q)$| $6$ |3| $C_{i}=1\ (1 \leq i \leq H), Q \leq 5$| $15$| |4| $C_{i}=1\ (1 \leq i \leq H), T_{k}=2\ (1 \leq k \leq Q)$| $11$| |5| $C_{i}=1\ (1 \leq i \leq H)$| $6$| |6| $Q \leq 5$| $12$| |7| $T_{k}=2\ (1 \leq k \leq Q)$| $26$| |8| 无附加限制 |$14$|

Samples

Input #1

Output #1

Input #2

Output #2

Input #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

Output #3

3
2
4

Input #4

Output #4

1
2
5

Input #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

Output #5

4
1

API Response (JSON)

{
  "problem": {
    "name": "[JOI 2024 Final] 路网服务 2 / Road Service 2",
    "description": {
      "content": "JOI 市有一个由 $H$ 条东西向的无限长道路和 $W$ 条南北向的道路组成的网格状道路网。从北边数第 $i\\ (1 \\leq i \\leq H)$ 条的东西向的道路和从西边数第 $j\\ (1 \\leq j \\leq W)$ 条的南北向的道路相交的地方称作交叉点 $(i, j)$。 现在，由于道路年久失修，一部分道路被封锁了。具体的封锁情况如下： - 如果 $A_{i, j}=0\\ (1 \\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10209"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JOI 市有一个由 $H$ 条东西向的无限长道路和 $W$ 条南北向的道路组成的网格状道路网。从北边数第 $i\\ (1 \\leq i \\leq H)$ 条的东西向的道路和从西边数第 $j\\ (1 \\leq j \\leq W)$ 条的南北向的道路相交的地方称作交叉点 $(i, j)$。\n\n现在，由于道路年久失修，一部分道路被封锁了。具体的封锁情况如下：\n\n- 如果 $A_{i, j}=0\\ (1 \\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments