Bessie's Function | Code Joint

Bessie has a special function $f (x)$ that takes as input an integer in $[1, N]$ and returns an integer in $[1, N]$ ( $1 \leq N \leq 2 \cdot 1 0^{5}$ ). Her function $f (x)$ is defined by $N$ integers $a_{1} \dots a_{N}$ where $f (x) = a_{x}$ ( $1 \leq a_{i} \leq N$ ).

Bessie wants this function to be idempotent. In other words, it should satisfy $f (f (x)) = f (x)$ for all integers $x \in [1, N]$ .

For a cost of $c_{i}$ , Bessie can change the value of $a_{i}$ to any integer in $[1, N]$ ( $1 \leq c_{i} \leq 1 0^{9}$ ). Determine the minimum total cost Bessie needs to make $f (x)$ idempotent.

We can change $a_{1} = 4$ , $a_{4} = 4$ , $a_{5} = 4$ . Since all $c_{i}$ equal one, the total cost is equal to $3$ , the number of changes. It can be shown that there is no solution with only $2$ or fewer changes.

We change $a_{3} = 3$ and $a_{4} = 4$ . The total cost is $2 + 5 = 7$ .

SCORING:

Subtasks:

Input 3: $N \leq 20$
Inputs 4-9: $a_{i} \geq i$
Inputs 10-15: All $a_{i}$ are distinct.
Inputs 16-21: No additional constraints.

Additionally, in each of the last three subtasks, the first half of tests will satisfy $c_{i} = 1$ for all $i$ .

Problem credits: Avnith Vijayram

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ .

The second line contains $N$ space-separated integers $a_{1}, a_{2}, \dots, a_{N}$ .

The third line contains $N$ space-separated integers $c_{1}, c_{2}, \dots, c_{N}$ .

Output Format

Output the minimum total cost Bessie needs to make $f (x)$ idempotent.

Sample Input 1

5 2 4 4 5 3 1 1 1 1 1

Sample Output 1

3

Sample Input 2

8 1 2 5 5 3 3 4 4 9 9 2 5 9 9 9 9

Sample Output 2

7

Submit

Language