| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 22 | 14 | 14 | 70.000% |
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.
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 the minimum total cost Bessie needs to make $f(x)$ idempotent.
5 2 4 4 5 3 1 1 1 1 1
3
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.
8 1 2 5 5 3 3 4 4 9 9 2 5 9 9 9 9
7
We change $a_3 = 3$ and $a_4 = 4$. The total cost is 2ドル+5=7$.