Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) 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. If you get a score $\gt 100$, feel free to contact the problem porter to update the testdata.

Problem Description

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.

Input Format

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.

Output Format

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.

0 2
2 3 1 1 2 2
3 3 1 1 3 3

*--o--o
      |
o  *--o
*  o--o
|  |  |
o  o  o
|  |  |
o--o  *

0 2
2 3 1 1 2 2
3 3 1 1 3 3

*--o  o
   |
o  *  o
*  o  o
|
o  o--o
|  |  |
o--o  *

1 2
2 3 1 1 2 2
3 3 1 1 3 3

5
9

Hint

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)$。

[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

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