CF1121A.Technogoblet of Fire

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Everybody knows that the mm-coder Tournament will happen soon. mm schools participate in the tournament, and only one student from each school participates.

There are a total of nn students in those schools. Before the tournament, all students put their names and the names of their schools into the Technogoblet of Fire. After that, Technogoblet selects the strongest student from each school to participate.

Arkady is a hacker who wants to have kk Chosen Ones selected by the Technogoblet. Unfortunately, not all of them are the strongest in their schools, but Arkady can make up some new school names and replace some names from Technogoblet with those. You can't use each made-up name more than once. In that case, Technogoblet would select the strongest student in those made-up schools too.

You know the power of each student and schools they study in. Calculate the minimal number of schools Arkady has to make up so that kk Chosen Ones would be selected by the Technogoblet.

众所周知,mm-coder 大赛即将举行。共有 mm 所学校参赛,每所学校仅有一名学生代表参赛。

这些学校一共有 nn 名学生。大赛开始前,所有学生将自己的姓名及其所在学校名称投入“科技高脚杯”(Technogoblet of Fire)中。随后,“科技高脚杯”将从每所学校中选出实力最强的学生参赛。

Arkady 是一名黑客,他希望让 kk 名“天选之人”(Chosen Ones)被“科技高脚杯”选中。遗憾的是,并非所有这 kk 名学生都是各自所在学校的最强者;但 Arkady 可以虚构一些新的学校名称,并用这些虚构的校名替换“科技高脚杯”中部分原有的校名。每个虚构的校名至多只能使用一次。此时,“科技高脚杯”也会为这些虚构的学校分别选出其中实力最强的学生。

你已知每名学生的实力值以及他们所在的学校。请计算 Arkady 至少需要虚构多少所学校,才能确保这 kk 名“天选之人”全部被“科技高脚杯”选中。

输入格式

The first line contains three integers nn, mm and kk (1≤n≤1001 \le n \le 100, 1≤m,k≤n1 \le m, k \le n) — the total number of students, the number of schools and the number of the Chosen Ones.

The second line contains nn different integers p1,p2,…,pnp_1, p_2, \ldots, p_n (1≤pi≤n1 \le p_i \le n), where pip_i denotes the power of ii-th student. The bigger the power, the stronger the student.

The third line contains nn integers s1,s2,…,sns_1, s_2, \ldots, s_n (1≤si≤m1 \le s_i \le m), where sis_i denotes the school the ii-th student goes to. At least one student studies in each of the schools.

The fourth line contains kk different integers c1,c2,…,ckc_1, c_2, \ldots, c_k (1≤ci≤n1 \le c_i \le n) — the id's of the Chosen Ones.

第一行包含三个整数 nn、mm 和 kk(1≤n≤1001 \le n \le 100,1≤m,k≤n1 \le m, k \le n)—— 分别表示学生的总人数、学校的数量以及“天选之人”的数量。

第二行包含 nn 个互不相同的整数 p1,p2,…,pnp_1, p_2, \ldots, p_n(1≤pi≤n1 \le p_i \le n),其中 pip_i 表示第 ii 位学生的实力值。实力值越大,学生越强。

第三行包含 nn 个整数 s1,s2,…,sns_1, s_2, \ldots, s_n(1≤si≤m1 \le s_i \le m),其中 sis_i 表示第 ii 位学生所属的学校。每所学校至少有一名学生。

第四行包含 kk 个互不相同的整数 c1,c2,…,ckc_1, c_2, \ldots, c_k(1≤ci≤n1 \le c_i \le n)—— 表示“天选之人”的编号。

输出格式

Output a single integer — the minimal number of schools to be made up by Arkady so that kk Chosen Ones would be selected by the Technogoblet.

输出一个整数——Arkady 需要组建的最少学校数量,使得 Technogoblet 能够选出 kk 位“被选中者”。

输入输出样例

  • 输入#1

    7 3 1
    1 5 3 4 6 7 2
    1 3 1 2 1 2 3
    3

    输出#1

    1
  • 输入#2

    8 4 4
    1 2 3 4 5 6 7 8
    4 3 2 1 4 3 2 1
    3 4 5 6

    输出#2

    2

说明/提示

In the first example there's just a single Chosen One with id 33. His power is equal to 33, but in the same school 11, there's a student with id 55 and power 66, and that means inaction would not lead to the latter being chosen. If we, however, make up a new school (let its id be 44) for the Chosen One, Technogoblet would select students with ids 22 (strongest in 33), 55 (strongest in 11), 66 (strongest in 22) and 33 (strongest in 44).

In the second example, you can change the school of student 33 to the made-up 55 and the school of student 44 to the made-up 66. It will cause the Technogoblet to choose students 88, 77, 66, 55, 33 and 44.

在第一个例子中,只有一位“天选之人”,其编号为 33。他的能力值为 33,但在同一所学校 11 中,还存在一名编号为 55、能力值为 66 的学生;这意味着若不采取任何行动,后者将被选中,而非前者。然而,如果我们为这位“天选之人”新建一所学校(设其编号为 44),则 Technogoblet 将选出以下学生:编号 22(学校 33 中最强者)、编号 55(学校 11 中最强者)、编号 66(学校 22 中最强者)以及编号 33(学校 44 中最强者)。

在第二个例子中,你可以将学生 33 的所属学校更改为新建的学校 55,并将学生 44 的所属学校更改为新建的学校 66。这将导致 Technogoblet 选出学生 88、77、66、55、33 和 44。

输入解题思路,AI测评打分。不知道怎么写?

首页