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:
- 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.
- 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.
- 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?
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.
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 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
Sample Input 2
5 6 4 0 4 1 1 4 2 5 3 2 2
Sample Output 2
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.
Point Value: 15 (partial)
Time Limit: 5.00s
Memory Limit: 128M
Added: Mar 22, 2019
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)It's quiet in here...