Multiverse Of Courier Service

Peregrine_Falcon Criterion 2022 Round 18
Limits 1s, 512 MB

Dr. Strange finally discovered a safe way to travel between parallel universes. By noticing people’s interests, he decided to start a courier business between two parallel universes named AA and BB. There are NN habitable planets in both AA and BB numbered from 11 to NN. For each ii, from 11 to NN, let’s call ithi^{th} planet AiA_i for universe AA and BiB_i for universe BB.

Dr. Strange appointed NN agents numbered from 11 to NN. For universe AA, each planet will host exactly one agent. And each agent will be appointed to exactly one planet. The same goes for universe BB. So, for each jj from 11 to NN, the jthj^{th} agent will be appointed to exactly one planet from universe AA and one planet from universe BB.

Dr. Strange initially created some routes between universes AA and BB. For each ii, there will be a direct route between AiA_i and BiB_i. For each jj, the jthj^{th} agent is appointed on one planet from AA and one planet from BB. These two planets are connected through a direct route. Using these routes, one planet may or may not get connected to many other planets using a series of routes.

Now Dr. Strange wants each planet to be connected to all other planets using one or more routes. Now, he may need to create some new routes. For each ii, planets AiA_i and BiB_i have a price tag PiP_i. Amount PiP_i needs to be paid if he wants to create a route and connect AiA_i or BiB_i with that route. For example, if he wants to create a route between AiA_i and AjA_j, he has to pay PiP_i ++ PjP_j amount of money.

What is the minimum amount of money that needs to spent, if he wants to make all the planets connected?


The first line on input will consist of an integer NN (1N5×105)(1 \leq N \leq 5×10^5).

The second line will consist of NN integers. The ithi^{th} integer GiAG_{i_A} (1GiAN)(1 \leq G_{i_A} \leq N) will represent the agent's identifier that will be appointed on the planet AiA_i.

The next line will consist of N integers. The ithi^{th} integer GiBG_{i_B} (1GiBN)(1 \leq G_{i_B} \leq N) will represent the agent’s identifier that will be appointed on the planet BiB_i.

The fourth line will consist of NN integers PiP_i​ (1Pi109)(1 \leq P_i \leq 10^9).


Print one integer, the minimum possible amount of money Dr. Strange has to pay in order to make each planet accessible to all other planets.


3 4 1 2
4 3 1 2
4 4 4 4

Dr. Strange can create a route between planets 11 and 33. Then another route between planets 11 and 22. So, he needs to pay amount 88 to planet 11, amount 44 to planet 22, and amount 44 to planet 33.


Login to submit.


61% Solution Ratio
curly_bracesEarliest, Jul '22
steinumFastest, 0.0s
steinumLightest, 52 kB
steinumShortest, 847B
Toph uses cookies. By continuing you agree to our Cookie Policy.