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 \ne 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:
- 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 \le 50~, ~M \le 50~, and ~D_i > 0~ for each ~i~.
In test cases worth another ~6/28~ of the points, ~N \le 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~.
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 \dots N~.
~M~ lines follow, the ~i~-th of which consists of a single integer, ~L_i~, for ~i = 1 \dots 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.