道路網の整備2 (Road Service 2)

JOI 市には,無限に長いH 本の東西方向の道路とW 本の南北方向の道路からなる格子状の道路網がある.
北からi 本目(\(1 \le i \le H\)) の東西方向の道路と,西からj 本目(\(1 \le j \le W\)) の南北方向の道路が交わる交差
点を交差点(i, j) と呼ぶことにする.
現在,道路の一部は整備不良により通行止めになっている.具体的な通行止めの状況は以下の通りで
ある.
• 北からi 本目(\(1 \le i \le H\)) の東西方向の道路の,交差点(i, j) と交差点(i, j + 1) を繋ぐ部分(1 ≦j ≦
W −1) は,Ai, j = 0 のとき通行止めで,Ai,j = 1 のとき通行可能である.
• 西からj 本目(\(1 \le j \le W\)) の南北方向の道路の,交差点(i, j) と交差点(i + 1, j) を繋ぐ部分
(1 ≦i ≦H −1) は,Bi,j = 0 のとき通行止めで,Bi, j = 1 のとき通行可能である.
• 道路のその他の部分,すなわち\(H \times W\) 個の交差点の外側の部分はすべて通行止めである.
JOI 市の市長であるK 理事長は,この道路網の整備計画を作ることにした.整備計画は,0 回以上の整備
からなる.1 回の整備では,\(1 \le i \le H\) を満たす整数i を1 つ選び,以下のことを行う:
1 ≦j ≦W −1 を満たすすべての整数j について,北からi 本目の東西方向の道路の,交差点(i, j) と
交差点(i, j + 1) を繋ぐ部分を(もし通行止めであれば)通行可能にする.これには全体でCi 日間か
かる.ただし,Ci は1 または2 である.
整備計画に含まれる複数の整備を同時に並行して行うことはできない.したがって,整備計画の実行に必
要な日数は,整備計画に含まれるすべての整備にかかる日数の合計である.
K 理事長は,まず市の重要施設の間を行き来できるようにするため,あなたにQ 個の質問をした.k 個
目(\(1 \le k \le Q\)) の質問は以下のようなものである.
Tk 個の交差点(Xk,1, Yk,1), (Xk,2, Yk,2), . . . , (Xk,Tk, Yk,Tk) の間を,道路の通行可能な部分のみを通って行
き来できるようにするような整備計画は存在するか.存在するならば,そのような整備計画の実行に
必要な日数として考えられる最小値は何日間か.
道路網の通行止めの状況,東西方向の各道路の整備にかかる日数,K 理事長の質問の内容が与えられたと
き,K 理事長の質問にすべて答えるプログラムを作成せよ.

第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)

• \(2 \le H\).
• \(2 \le W\).
• H × W ≦1 000 000.
• 1 ≦Q ≦100 000.
• Ai,j は0 または1 (1 ≦i ≦H, 1 ≦j ≦W −1).
• Bi,j は0 または1 (1 ≦i ≦H −1, 1 ≦j ≦W).
• Ci は1 または2 (\(1 \le i \le H\)).
• \(2 \le Tk\) (\(1 \le k \le Q\)).
• T1 + T2 + · · · + TQ ≦200 000.
• \(1 \le Xk,l \le H\) (\(1 \le k \le Q, 1 \le l \le Tk\)).
• \(1 \le Yk,l \le W\) (\(1 \le k \le Q, 1 \le l \le Tk\)).
• (Xk,1, Yk,1), (Xk,2, Yk,2), . . . , (Xk,Tk, Yk,Tk) は相異なる(\(1 \le k \le Q\)).
• 入力される値はすべて整数である.

1. (10 点) Ci = 1 (\(1 \le i \le H\)),Q ≦5,Tk = 2 (\(1 \le k \le Q\)),Ai,j = 0 (1 ≦i ≦H, 1 ≦j ≦W −1).
2. (6 点) Ci = 1 (\(1 \le i \le H\)),Q ≦5,Tk = 2 (\(1 \le k \le Q\)).
3. (15 点) Ci = 1 (\(1 \le i \le H\)),\(Q \le 5\).
4. (11 点) Ci = 1 (\(1 \le i \le H\)),Tk = 2 (\(1 \le k \le Q\)).
5. (6 点) Ci = 1 (\(1 \le i \le H\)).
6. (12 点) \(Q \le 5\).
7. (26 点) Tk = 2 (\(1 \le k \le Q\)).
8. (14 点) 追加の制約はない.

第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)

入力は以下の形式で標準入力から与えられる.
H W Q
A1,1A1,2 · · · A1,W−1
A2,1A2,2 · · · A2,W−1
...
AH,1AH,2 · · · AH,W−1
B1,1B1,2 · · · B1,W
B2,1B2,2 · · · B2,W
...
BH−1,1BH−1,2 · · · BH−1,W
C1 C2 · · · CH
Query1
Query2
...
QueryQ
ただし,各Queryk (\(1 \le k \le Q\)) は以下の形式である.
Tk
Xk,1 Yk,1
Xk,2 Yk,2
...
Xk,Tk Yk,Tk

標準出力にQ 行で出力せよ.k 行目(\(1 \le k \le Q\)) には,Tk 個の交差点(Xk,1, Yk,1), (Xk,2, Yk,2), . . . , (Xk,Tk, Yk,Tk)
の間を,道路の通行可能な部分のみを通って行き来できるようにするような整備計画が存在するならば,そ
のような整備計画の実行に必要な日数の最小値を出力し,そうでないならば-1 を出力せよ.

第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)

생성자가 기록되지 않았습니다.

출처 JOI 2024 Final