#PU1497. USACO 2025 February Contest, Gold — Problem 1. Bessie's Function

    ID: 1430 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb25来源:usaco.orgscoring:equal_test_cases贪心枚举

USACO 2025 February Contest, Gold — Problem 1. Bessie's Function

USACO 2025 February Contest, Gold — Problem 1. Bessie's Function

题目描述

Bessie has a special function f(x)f(x) that takes as input an integer in [1,N][1, N] and returns an integer in [1,N][1, N] (1≤N≤2⋅1051 \le N \le 2 \cdot 10^5). Her function f(x)f(x) is defined by NN integers a1…aNa_1 \ldots a_N where f(x)=axf(x) = a_x (1≤ai≤N1 \le a_i \le N). Bessie wants this function to be idempotent. In other words, it should satisfy f(f(x))=f(x)f(f(x)) = f(x) for all integers x∈[1,N]x \in [1, N]. For a cost of cic_i, Bessie can change the value of aia_i to any integer in [1,N][1, N] (1≤ci≤1091 \le c_i \le 10^9). Determine the minimum total cost Bessie needs to make f(x)f(x) idempotent.

输入格式

The first line contains NN. The second line contains NN space-separated integers a1,a2,…,aNa_1,a_2,\dots,a_N. The third line contains NN space-separated integers c1,c2,…,cNc_1,c_2,\dots,c_N.

输出格式

(见题面原文)

数据范围

Subtasks:

样例

样例 1

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.

样例 2

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$.