WC '18 Contest 4 S3 - Dance Royale

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 128M

Author:
Problem type
Woburn Challenge 2018-19 Round 4 - Senior Division

Billy is trying his hand at the latest popular game taking the world by storm: Dance Royale.

In Dance Royale, there are N (1 \le N \le 300\,000) locations on a map (numbered from 1 to N). Each location i has a destination number D_{i} (0 \le D_{i} \le N, D_{i} \neq i), which is used during gameplay (as described below).

There are also M (2 \le M \le 300\,000) players, with the i-th player beginning the game at location L_{i} (1 \le L_{i} \le N). Each player has some sick dance moves.

The game proceeds in sets of three phases as follows:

  1. For each unordered pair of players still in the game, if they are currently at the same location and have not yet had a dance-off against one another, then they engage in a dance-off against one another. Nobody is harmed in the process, a good time is simply had.
  2. For each player still in the game, let d be their current location's destination number. If d = 0, then they're forced to permanently leave the game. Otherwise, they move to location d.
  3. If there are fewer than 2 players left in the game, then the game ends. Otherwise, the process repeats itself from phase 1.

Note that the game may last forever, which is fine — Billy is accustomed to extended periods of mental focus.

After the game has either ended or has gone on for an infinite amount of time, how many dance-offs will end up having taken place in total?

Subtasks

In test cases worth 6/28 of the points, N \leq 50, M \leq 50, and D_{i} > 0 for each i.
In test cases worth another 6/28 of the points, N \leq 2\,000, and D_{i} > 0 for each i.
In test cases worth another 10/28 of the points, D_{i} > 0 for each i.

Input Specification

The first line of input consists of two space-separated integers, N and M.
N lines follow, the i-th of which consists of a single integer, D_{i}, for i = 1\ldots N.
M lines follow, the i-th of which consists of a single integer, L_{i}, for i = 1\ldots M.

Output Specification

Output a single integer, the number of dance-offs which will take place.

Sample Input 1

4 4
4
3
1
3
4
2
3
4

Sample Output 1

3

Sample Input 2

5 6
4
0
4
1
1
4
2
5
3
2
2

Sample Output 2

4

Sample Explanation

In the first case:

  • Right off the bat, a dance-off will occur between players 1 and 4, as they both occupy location 4.
  • Then, in the second cycle of the phases, players 1, 2, and 4 will all find themselves at location 3, resulting in player 2 having dance-offs with both players 1 and 4. Note that players 1 and 4 will not repeat their dance-off against one another.
  • The game will end up continuing forever with all 4 players in action, but no more dance-offs will ever take place.

In the second case:

  • Right off the bat, dance-offs will occur between player pairs (2,
5), (2, 6), and (5, 6), due to players 2, 5, and 6 all occupying location 2. These 3 players will then leave the game in phase 2.
  • Then, in the second cycle of the phases, players 1 and 3 will both find themselves at location 1 and will therefore have a dance-off.
  • The game will end up continuing forever with 3 players remaining, but no more dance-offs will ever take place.

Comments

There are no comments at the moment.