P10874 [COTS 2022] Journey Dugput (Unofficial testdata).

Translated from [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T1。$\texttt{5s,0.5G}$。 - **The input format is slightly adjusted.** - **The official testdata is incorrect.** Some out files were generated using the code of “Tree Sister” [hhoppitree](https://www.luogu.com.cn/user/183609). If you get a score $\gt 100$, feel free to contact the problem porter to update the testdata.

Construct an $N \times M$ grid graph where all edge weights are $1$, and each edge may exist or not exist. Under the condition that the graph is connected, maximize the shortest path length from $(A,B)$ to $(C,D)$. **Here, the path length is defined as the number of nodes visited by the path.**

**This problem contains multiple test cases within a single test point.** The first line contains two integers $\mathrm{type},T$, representing the testdata type and the number of test cases. The next $T$ lines each contain $6$ integers $N,M,A,B,C,D$, with meanings as described in the statement.

For each test case, output several lines. - $\mathrm{type}=0$: “Construction” type testdata. For this type, you need to construct a grid graph. Output $(2N-1)$ lines, each with $(3M-2)$ characters. In line $(2i-1)$, the character at position $(3j-2)$ represents the vertex $(i,j)$. When $(i,j)=(A,B)$ or $(S,T)$, print `*` (ASCII 42); otherwise print `o` (ASCII 111). For two vertices $(i,j)$ and $(i,j+1)$ in the same row, if there is an edge, fill the two spaces between them with `--` (ASCII 45); otherwise, leave them unfilled. For two vertices $(i,j)$ and $(i+1,j)$ in the same column, if there is an edge, fill the one space between them with `|` (ASCII 124); otherwise, leave it unfilled. All unfilled areas should be padded with spaces. Do not output extra spaces or blank lines. See the sample output. - $\mathrm{type}=1$: “Traditional” type testdata. You only need to output one line with one integer, representing the shortest possible value of the maximum shortest path length.

For $100\%$ of the testdata, it is guaranteed that: - $1\le N,M\le 5\, 000$； - $1\le T\le 1\, 600$； - $1\le A,C\le N$，$1\le B,D\le M$； - $(A,B)\neq (C,D)$。 | Subtask ID | $N\cdot M\in $ | $M\le $ | $\mathrm{type}=$ | Score | |:-----:|:------:| :----: | :--: | :--: | | $1$ | $[2,100]$ | $5\, 000$ | $0$ | $20$ | | $2$ | $[2,1\, 000]$ | $5\, 000$ | $0$ | $25$ | | $3$ | $[2,15\, 000]$ | $3$ | $0$ | $15$ | | $4$ | $[2,100\, 000]$ | $5\, 000$ | $0$ | $25$ | | $5$ | $[2,100\, 000]$ | $5\, 000$ | $1$ | $15$ | [Scoring] - $\mathrm{type}=0$: “Construction” type testdata. Let $d_i$ be the shortest path length in the construction you output for the $i$-th test case, and let $D_i$ be the maximum possible shortest path length. Define $$K=\frac{1}{Q}\sum_{i=1}^Q\frac{d_i}{D_i}$$ When $K=1$, you get full score for this test point; otherwise, you get $0.7\cdot K$ times the score of this test point. The score of each subtask is the $\min$ over the scores of all test points. For example, the output of Sample 1 gets full score; for Sample 2, $\displaystyle k=\frac{1}{2}\left(\frac{3}{5}+\frac{5}{9}\right)=\frac{31}{45}$, so you will get $\displaystyle 0.7\cdot \frac{31}{45}\approx 0.482$ times the score of this test point. - $\mathrm{type}=1$: “Traditional” type testdata. Same as the standard scoring method for traditional problems. Translated by ChatGPT 5