USACO

USACO 2025 February Contest, Gold

Problem 1. Bessie's Function

Contest has ended.

Log in to allow submissions in analysis mode

Bessie has a special function $f(x)$ that takes as input an integer in $[1, N]$ and returns an integer in $[1, N]$ ( $1 \le N \le 2 \cdot 10^5$ ). Her function $f(x)$ is defined by $N$ integers $a_1 \ldots a_N$ where $f(x) = a_x$ ( $1 \le a_i \le 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 \le c_i \le 10^9$ ). Determine the minimum total cost Bessie needs to make $f(x)$ idempotent.

INPUT FORMAT (input arrives from the terminal / stdin):

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 (print output to the terminal / stdout):

Output the minimum total cost Bessie needs to make

$f(x)$ idempotent.

SAMPLE INPUT:

5
2 4 4 5 3
1 1 1 1 1

SAMPLE OUTPUT:

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.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

We change $a_3 = 3$ and $a_4 = 4$ . The total cost is $2+5=7$ .

SCORING:

Subtasks:

Input 3: $N\le 20$
Inputs 4-9: $a_i\ge 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

Contest has ended. No further submissions allowed.