IOI '21 P5 - Dungeons Game

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem types
Allowed languages
C++

Robert is designing a new computer game. The game involves one hero, n opponents and n + 1 dungeons. The opponents are numbered from 0 to n - 1 and the dungeons are numbered from 0 to n. Opponent i (0 \le i \le n - 1) is located in dungeon i and has strength s[i]. There is no opponent in dungeon n.

The hero starts off entering dungeon x, with strength z. Every time the hero enters any dungeon i (0 \le i \le n - 1), they confront opponent i, and one of the following occurs:

  • If the hero's strength is greater than or equal to the opponent's strength s[i], the hero wins. This causes the hero's strength to increase by s[i] (s[i] \ge 1). In this case the hero enters dungeon w[i] next (w[i] > i).
  • Otherwise, the hero loses. This causes the hero's strength to increase by p[i] (p[i] \ge 1). In this case the hero enters dungeon l[i] next.

Note p[i] may be less than, equal to, or greater than s[i]. Also, l[i] may be less than, equal to, or greater than i. Regardless of the outcome of the confrontation, the opponent remains in dungeon i and maintains strength s[i].

The game ends when the hero enters dungeon n. One can show that the game ends after a finite number of confrontations, regardless of the hero's starting dungeon and strength.

Robert asked you to test his game by running q simulations. For each simulation, Robert defines a starting dungeon x and starting strength z. Your task is to find out, for each simulation, the hero's strength when the game ends.

Implementation Details

You should implement the following procedures:

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
  • n: number of opponents.
  • s, p, w, l: arrays of length n. For 0 \le i \le n - 1:
    • s[i] is the strength of the opponent i. It is also the strength gained by the hero after winning against opponent i.
    • p[i] is the strength gained by the hero after losing against opponent i.
    • w[i] is the dungeon the hero enters after winning against opponent i.
    • l[i] is the dungeon the hero enters after losing against opponent i.
  • This procedure is called exactly once, before any calls to simulate (see below).
long long simulate(int x, int z)
  • x: the dungeon the hero enters first.
  • z: the hero's starting strength.
  • This procedure should return the hero's strength when the game ends, assuming the hero starts the game by entering dungeon x, having strength z.
  • The procedure is called exactly q times.

Examples

Consider the following call:

init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1})

The diagram above illustrates this call. Each square shows a dungeon. For dungeons 0, 1 and 2, the values s[i] and p[i] are indicated inside the squares. Magenta arrows indicate where the hero moves after winning a confrontation, while black arrows indicate where the hero moves after losing.

Let's say the grader calls simulate(0, 1).

The game proceeds as follows:

Dungeon Hero's strength before confrontation Result
0 1 Lose
1 4 Lose
0 5 Win
2 7 Lose
1 9 Win
2 15 Win
3 24 Game ends

As such, the procedure should return 24.

Let's say the grader calls simulate(2, 3).

The game proceeds as follows:

Dungeon Hero's strength before confrontation Result
2 3 Lose
1 5 Lose
0 6 Win
2 8 Lose
1 10 Win
2 16 Win
3 25 Game ends

As such, the procedure should return 25.

Constraints

  • 1 \le n \le 400\,000
  • 1 \le q \le 50\,000
  • 1 \le s[i], p[i] \le 10^7 (for all 0 \le i \le n - 1)
  • 0 \le l[i], w[i] \le n (for all 0 \le i \le n - 1)
  • w[i] > i (for all 0 \le i \le n - 1)
  • 0 \le x \le n - 1
  • 1 \le z \le 10^7

Subtasks

  1. (11 points) n \le 50\,000,\ q \le 100,\ s[i], p[i] \le 10\,000 (for all 0 \le i \le n - 1)
  2. (26 points) s[i] = p[i] (for all 0 \le i \le n - 1)
  3. (13 points) n \le 50\,000, all opponents have the same strength, in other words, s[i] = s[j] for all 0 \le i, j \le n - 1.
  4. (12 points) n \le 50\,000, there are at most 5 distinct values among all values of s[i].
  5. (27 points) n \le 50\,000
  6. (11 points) No additional constraints.

Sample Grader

The sample grader reads the input in the following format:

  • line 1: n \ q
  • line 2: s[0] \ s[1] \ \dots \ s[n - 1]
  • line 3: p[0] \ p[1] \ \dots \ p[n - 1]
  • line 4: w[0] \ w[1] \ \dots \ w[n - 1]
  • line 5: l[0] \ l[1] \ \dots \ l[n - 1]
  • line 6 + i (0 \le i \le q - 1): x \ z for the i-th call to simulate.

The sample grader prints your answers in the following format:

  • line 1 + i (0 \le i \le q - 1): the return value of the i-th call to simulate.

Attachment Package

The sample grader and sample test cases are available here: dungeons.zip.


Comments


  • 1
    TechnobladeNeverDies  commented on July 22, 2021, 2:02 p.m. edited

    edit: sorry it seems that it can't be 2GB for system reasons :(

    ML should be 2GB.