Woburn Challenge 2018-19 Round 4 - Senior Division

Problem 3: Dance Royale

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

In Dance Royale, there are N (1 ≤ N ≤ 300,000) locations on a map (numbered from 1 to N). Each location i has a destination number Di (0 ≤ Di ≤ N, Di ≠ i), which is used during gameplay (as described below).

There are also M (2 ≤ M ≤ 300,000) players, with the i-th player beginning the game at location Li (1 ≤ Li ≤ 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 ≤ 50, M ≤ 50, and Di > 0 for each i.
In test cases worth another 6/28 of the points, N ≤ 2000, and Di > 0 for each i.
In test cases worth another 10/28 of the points, Di > 0 for each i.

Input Format

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, Di, for i = 1..N.
M lines follow, the i-th of which consists of a single integer, Li, for i = 1..M.

Output Format

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.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 5.00s
Memory Limit: 128M
Added: Mar 22, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...