## IOI '14 P1 - Rail

View as PDF

Points: 30 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++

Taiwan has a big railway line connecting the western and eastern shores of the island. The line consists of blocks. The consecutive blocks are numbered , starting from the western end. Each block has a one-way west-bound track on the north, a one-way east-bound track on the south, and optionally a train station between them.

There are three types of blocks. A type C block has a train station that you must enter from the northern track and exit to the southern track, a type D block has a train station that you must enter from the southern track and exit to the northern track, and a type empty block has no train station. For example, in the following figure block is type empty, block is type C, and block is type D. Blocks connect to each other horizontally. Tracks of adjacent blocks are joined by connectors, shown as shaded rectangles in the following figure.

The rail system has stations numbered from to . We assume that we can go from any station to any other station by following the track. For example we can go from station to station by starting from block , then passing through blocks and by the southern track, and then passing through station , then passing through block by the northern track, and finally reaching station at block .

Since there are multiple possible routes, the distance from one station to another is defined as the minimum number of connectors the route passes through. For example the shortest route from station to is through blocks and passes through connectors, so the distance is .

A computer system manages the rail system. Unfortunately after a power outage the computer no longer knows where the stations are and what types of blocks they are in. The only clue the computer has is the block number of station , which is always in a type C block. Fortunately the computer can query the distance from any station to any other station. For example, the computer can query 'what is the distance from station to station ?' and it will receive .

You need to implement a function findLocation that determines for each station the block number and block type.

• findLocation(n, first, location, stype)
• n: the number of stations.
• first: the block number of station .
• location: array of size ; you should place the block number of station into location[i].
• stype: array of size ; you should place the block type of station into stype[i]: for type C and for type D.

You can call a function getDistance to help you find the locations and types of stations.

• getDistance(i, j) returns the distance from station to station . getDistance(i, i) will return . getDistance(i, j) will return if or is outside the range .

In all subtasks the number of blocks is no more than . In some subtasks the number of calls to getDistance is limited. The limit varies by subtask. Your program will receive 'wrong answer' if it exceeds this limit.

1 8 unlimited All stations except are in type D blocks.
2 22 unlimited All stations to the right of station are in type D blocks, and all stations to the left of station are in type C blocks.

#### Implementation details

You have to submit exactly one file. This file implements findLocation as described above using the following signature.

void findLocation(int n, int first, int location[], int stype[]);