P10209 [JOI 2024 Final] Road Service 2 / Road Service 2

JOI City has a grid-like road network consisting of $H$ infinitely long east–west roads and $W$ north–south roads. The intersection of the $i\ (1 \leq i \leq H)$-th east–west road counted from the north and the $j\ (1 \leq j \leq W)$-th north–south road counted from the west is called intersection $(i, j)$. Now, due to long-term disrepair, some road segments are blocked. The blocking status is as follows: - If $A_{i, j}=0\ (1 \leq i \leq H, 1 \leq j \leq W-1)$, then on the $i$-th east–west road counted from the north, the segment between intersections $(i, j)$ and $(i, j+1)$ is blocked. If $A_{i, j}=1$, then it is passable. - If $B_{i, j}=0\ (1 \leq j \leq W, 1 \leq i \leq H-1)$, then on the $j$-th north–south road counted from the west, the segment between intersections $(i, j)$ and $(i+1, j)$ is blocked. If $B_{i, j}=1$, then it is passable. - All other parts of the roads, namely the parts outside the $H \times W$ intersections, are blocked. The city mayor, Director K, decided to make a road repair plan. A repair plan consists of at least $0$ repairs. In one repair, choose an integer $i\ (1 \leq i \leq H)$, and perform the following operation: For **all** integers $j$ satisfying $1 \leq j \leq W-1$, if on the $i$-th east–west road counted from the north the segment between intersections $(i, j)$ and $(i, j+1)$ is blocked, make it passable. This process takes $C_i$ days in total, where $C_i$ is $1$ or $2$. Multiple repairs in the repair plan cannot be carried out at the same time. Therefore, the number of days required to execute the repair plan is the sum of the days required by all repairs included in the plan. To allow important facilities in the city to be mutually reachable, Director K asks you $Q$ questions. The $k$-th question $(1 \leq k \leq Q)$ is as follows: Is there a repair plan that makes the $T_k$ intersections $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ mutually reachable using only passable roads. If such a plan exists, what is the minimum number of days needed to execute such a repair plan. Given the blocking status of the road network, the days required to repair each road, and the contents of Director K's questions, write a program to answer all of Director K's questions.

The first line contains three integers $H,W,Q$. The next $H$ lines each contain a string of length $W-1$, representing $A_{i,1},A_{i,2},\ldots ,A_{i,W-1}$. The next $H-1$ lines each contain a string of length $W$, representing $B_{i,1},B_{i,2},\ldots ,B_{i,W}$. The next line contains $H$ space-separated integers $C_1,C_2,\ldots ,C_H$. Then there are $Q$ queries, each given in the following form: The first line contains an integer $T_k$. The next $T_k$ lines each contain two integers $X_{k,i},Y_{k,i}$.

Output $Q$ lines. In the $k$-th line $(1 \leq k \leq Q)$, if there exists a repair plan that makes the $T_k$ intersections $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ mutually reachable, output the minimum number of days needed to execute such a repair plan. Otherwise, output $-1$.

For all input data, it holds that: - $2 \leq H$. - $2 \leq W$. - $H \times W \leq 10^6$. - $1 \leq Q \leq 10^5$. - $A_{i, j}$ is $0$ or $1\ (1 \leq i \leq H, 1 \leq j \leq W-1)$. - $B_{i, j}$ is $0$ or $1\ (1 \leq i \leq H-1,1 \leq j \leq W)$. - $C_{i}$ is $1$ or $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}})$ are all distinct $(1 \leq k \leq Q)$. The detailed additional constraints and scores for subtasks are shown in the table below. |Subtask|Additional Constraints|Score| | :-: | :-: | :-:| |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|No additional constraints|$14$| Translated by ChatGPT 5