Description

Gardens by the Bay is a large nature park in Singapore. There are $n$ towers in the park, called “supertrees”. The towers are numbered from $0$ to $n-1$. We want to build a set of bridges (the number of bridges is at least $0$). Each bridge connects two different towers and can be traveled in both directions. No two bridges connect the same pair of towers.

A path from tower $x$ to tower $y$ is a sequence of towers (the number of towers is at least $1$) that satisfies the following:

• The first element of the sequence is $x$.
• The last element of the sequence is $y$.
• All elements in the sequence are distinct.

Each pair of adjacent elements (towers) in the sequence is connected by some bridge.

Note that by definition, there is exactly one path from a tower to itself, and for any towers $i$ and $j$, the number of different paths from tower $i$ to tower $j$ is the same as the number of different paths from tower $j$ to tower $i$.

The chief designer wants the bridges to satisfy the following: for any given $0 \le i,j \le n-1$, there are exactly $p[i][j]$ different paths from tower $i$ to tower $j$, where $0 \le p[i][j] \le 3$.

Please construct a set of bridges that satisfies the designer’s requirements, or determine that such a set of bridges cannot exist.

Implementation Details

You need to implement the following function:

int construct(std::vector<std::vector<int> > p)

• $p$: an $n \times n$ array describing the designer’s requirements.
• If such a construction exists, this function should call build (see below) exactly once to output the construction, and then return $1$.
• Otherwise, this function should return $0$ and must not call build.
• This function will be called exactly once.

The function build is defined as follows:

void build(std::vector<std::vector<int> > b)

• $b$: an $n \times n$ array, where $b[i][j]=1$ means there is a bridge connecting tower $i$ and tower $j$, and otherwise $b[i][j]=0$.
• Note that this array must satisfy: for all $0 \le i,j \le n-1$, $b[i][j]=b[j][i]$; and for all $0 \le i \le n-1$, $b[i][i]=0$.

Hint

Sample Explanation

Example 1

Consider the following call:

construct([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]])

This indicates that there is exactly one path from tower $0$ to tower $1$. For all other pairs of towers $(x,y)(0 \le x<y \le 3)$, there are exactly two different paths connecting tower $x$ and tower $y$. This can be achieved by building $4$ bridges: connecting the pairs $(0, 1), (1, 2), (1, 3)$, and $(2,3)$.

To output this solution, the function construct should make the following call:

build([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]])

The function should return $1$.

For this example, there are many different constructions that satisfy the requirements, and all of them are considered correct.

Example 2

Consider the following call:

construct([[1, 0], [0, 1]])

This indicates that it is impossible to travel between the two towers. This can only be satisfied by building no bridges.

Therefore, the function construct should make the following call:

build([[0, 0], [0, 0]])

Then, the function construct should return $1$.

Example 3

Consider the following call:

construct([[1, 3], [3, 1]])

This indicates that there are exactly $3$ paths from tower $0$ to tower $1$. These requirements cannot be satisfied. Therefore, the function construct should return $0$ and must not call build.

Constraints

• $1\le n\le 1000$
• $p[i][i]=1$ (for all $0 \le i \le n-1$)
• $p[i][j]=p[j][i]$ (for all $0 \le i,j \le n-1$)
• $0 \le p[i][j] \le 3$ (for all $0 \le i,j \le n-1$)

Subtasks

1. (11 points) $p[i][j]=1$ (for all $0 \le i,j \le n-1$).
2. (10 points) $p[i][j] \in \{0,1\}$ (for all $0 \le i,j \le n-1$).
3. (19 points) $p[i][j] \in \{0,2\}$ (for all $i \ne j,0 \le i,j \le n-1$).
4. (35 points) $0 \le p[i][j]\le 2$ (for all $0 \le i,j \le n-1$) and there exists at least one construction that satisfies the requirements.
5. (21 points) $0 \le p[i][j] \le 2$ (for all $0 \le i,j \le n-1$).
6. (4 points) No additional constraints.

Example Grader

The example grader reads the input in the following format:

Line $1$: $n$
Line $2+i$ ($0 \le i \le n+1$): $p[i][0]\ p[i][1]\ \ldots\ p[i][n]$

The output format of the example grader is as follows:

Line $1$: the return value of construct.

If the return value of construct is $1$, the example grader will additionally print:

Line $2+i$ ($0 \le i \le n+1$): $b[i][0]\ b[i][1]\ \ldots\ b[i][n]$

Translated by ChatGPT 5