P6830 [IOI 2020] Connecting Supertrees

**This is an interactive problem.** This problem only supports the C++ language family. When submitting, you **do not need** to include the `supertrees.h` header file, but you **must** include the `vector` header file at the beginning of your program and declare the function `void build(std::vector b);`

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: ```cpp int construct(std::vector 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: ```cpp void build(std::vector 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$.

N/A

N/A

#### Sample Explanation #### Example 1 Consider the following call: ```cpp 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