IOI '20 P2 - Connecting Supertrees

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type
Allowed languages
C++

Gardens by the Bay is a large nature park in Singapore. In the park there are nn towers, known as supertrees. These towers are labelled 00 to n - 1n - 1. We would like to construct a set of zero or more bridges. Each bridge connects a pair of distinct towers and may be traversed in either direction. No two bridges should connect the same pair of towers.

A path from tower xx to tower yy is a sequence of one or more towers such that:

  • the first element of the sequence is xx,
  • the last element of the sequence is yy,
  • all elements of the sequence are distinct, and
  • each two consecutive elements (towers) in the sequence are connected by a bridge.

Note that by definition there is exactly one path from a tower to itself and the number of different paths from tower ii to tower jj is the same as the number of different paths from tower jj to tower ii.

The lead architect in charge of the design wishes for the bridges to be built such that for all 0 \le i,j \le n - 10 \le i,j \le n - 1 there are exactly p[i][j]p[i][j] different paths from tower ii to tower jj, where 0 \le p[i][j] \le 30 \le p[i][j] \le 3.

Construct a set of bridges that satisfy the architect's requirements, or determine that it is impossible.

Implementation details

You should implement the following procedure:

int construct(int[][] p)
  • pp : an n \times nn \times n array representing the architect's requirements.
  • If a construction is possible, this procedure should make exactly one call to build (see below) to report the construction, following which it should return 11.
  • Otherwise, the procedure should return 00 without making any calls to build.
  • This procedure is called exactly once.

The procedure build is defined as follows:

void build(int[][] b)
  • bb : an n \times nn \times n array, with b[i][j] = 1b[i][j] = 1 if there is a bridge connecting tower ii and tower jj, or b[i][j] = 0b[i][j] = 0 otherwise.
  • Note that the array must satisfy b[i][j] = b[j][i]b[i][j] = b[j][i] for all 0 \le i,j \le n - 10 \le i,j \le n - 1 and b[i][i] = 0b[i][i] = 0 for all 0 \le i \le n - 10 \le i \le n - 1.

Examples

Example 1

Consider the following call:

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

This means that there should be exactly one path from tower 00 to tower 11. For all other pairs of towers (x, y)(x, y), such that 0 \le x < y \le 30 \le x < y \le 3, there should be exactly two paths from tower xx to tower yy. This can be achieved with 44 bridges, connecting pairs of towers (0, 1)(0, 1), (1, 2)(1, 2), (1, 3)(1, 3) and (2, 3)(2, 3).

To report this solution, the construct procedure should make the following call:

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

It should then return 11.

In this case, there are multiple constructions that fit the requirements, all of which would be considered correct.

Example 2

Consider the following call:

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

This means that there should be no way to travel between the two towers. This can only be satisfied by having no bridges.

Therefore, the construct procedure should make the following call:

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

After which, the construct procedure should return 11.

Example 3

Consider the following call:

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

This means that there should be exactly 33 paths from tower 00 to tower 11. This set of requirements cannot be satisfied. As such, the construct procedure should return 00 without making any call to build.

Constraints

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

Subtasks

  1. (1111 points) p[i][j] = 1p[i][j] = 1 ((for all 0 \le i,j \le n - 1)0 \le i,j \le n - 1)
  2. (1010 points) p[i][j] = 0p[i][j] = 0 or 11 ((for all 0 \le i,j \le n - 1)0 \le i,j \le n - 1)
  3. (1919 points) p[i][j] = 0p[i][j] = 0 or 22 ((for all 0 \le i,j \le n - 1)0 \le i,j \le n - 1)
  4. (3535 points) 0 \le p[i][j] \le 20 \le p[i][j] \le 2 ((for all 0 \le i,j \le n - 1)0 \le i,j \le n - 1) and there is at least one construction satisfying the requirements.
  5. (2121 points) 0 \le p[i][j] \le 20 \le p[i][j] \le 2 ((for all 0 \le i,j \le n - 1)0 \le i,j \le n - 1)
  6. (44 points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

  • line 11: nn
  • line 2 + i \ (0 \le i \le n - 1)2 + i \ (0 \le i \le n - 1): p[i][0] \ p[i][1] \ \dots \ p[i][n - 1]p[i][0] \ p[i][1] \ \dots \ p[i][n - 1]

The output of the sample grader is in the following format:

  • line 11: the return value of construct.

If the return value of construct is 11, the sample grader additionally prints:

  • line 2 + i \ (0 \le i \le n - 1)2 + i \ (0 \le i \le n - 1): b[i][0] \ b[i][1] \ \dots \ b[i][n - 1]b[i][0] \ b[i][1] \ \dots \ b[i][n - 1]

Comments

There are no comments at the moment.