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 $A$ and $B$. There are $N$ habitable planets in both $A$ and $B$ numbered from $1$ to $N$. For each $i$, from $1$ to $N$, let’s call $i^{th}$ planet $A_i$ for universe $A$ and $B_i$ for universe $B$.

Dr. Strange appointed $N$ agents numbered from $1$ to $N$. For universe $A$, each planet will host exactly one agent. And each agent will be appointed to exactly one planet. The same goes for universe $B$. So, for each $j$ from $1$ to $N$, the $j^{th}$ agent will be appointed to exactly one planet from universe $A$ and one planet from universe $B$.

Dr. Strange initially created some routes between universes $A$ and $B$. For each $i$, there will be a direct route between $A_i$ and $B_i$. For each $j$, the $j^{th}$ agent is appointed on one planet from $A$ and one planet from $B$. 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 $i$, planets $A_i$ and $B_i$ have a price tag $P_i$. Amount $P_i$ needs to be paid if he wants to create a route and connect $A_i$ or $B_i$ with that route. For example, if he wants to create a route between $A_i$ and $A_j$, he has to pay $P_i$ $+$ $P_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 $N$ $(1 \leq N \leq 5×10^5)$.

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

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

The fourth line will consist of $N$ integers $P_i$ $(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.

Input | Output |
---|---|

4 3 4 1 2 4 3 1 2 4 4 4 4 | 16 |

Dr. Strange can create a route between planets $1$ and $3$. Then another route between planets $1$ and $2$. So, he needs to pay amount $8$ to planet $1$, amount $4$ to planet $2$, and amount $4$ to planet $3$. |

Login to submit.

61%
Solution Ratio

curly_bracesEarliest,

steinumFastest, 0.0s

steinumLightest, 52 kB

steinumShortest, 847B

Toph uses cookies. By continuing you agree to our Cookie Policy.