我们建立了一个由编号为 $0,\dots ,n-1$ 的 $n$ 个人组成的社交网络。网络中的有些对会成为朋友。如果 $x$ 号人成为 $y$ 号人的朋友，则 $y$ 号人同时也会成为 $x$ 号人的朋友。

这些人将通过 $n$ 个阶段加入这个网络，阶段也编号为 $0$ 至 $n-1$。第 $i$ 号人在第 $i$ 个阶段加入。在阶段 $0$，$0$ 号人加入网络并成为唯一的人。此后 $n-1$ 个阶段的各个阶段，都有一个人会被主持人加入到网络中，而这个主持人可以是已在网络中的任何一个人。在阶段 $i$ 中 ($1\le i\le n-1$)，该阶段的主持人可以用如下三种方式之一把第 $i$ 号人加入到网络中：

• IAmYourFriend：将第 $i$ 号人仅变成主持人的朋友。
• MyFriendsAreYourFriends：将第 $i$ 号人变成主持人当前的每一个朋友的朋友。 注意，这个方式不会将第 $i$ 号人变成主持人的朋友。
• WeAreYourFriends：将第 $i$ 号人变成主持人的朋友，同时也变成主持人当前的每一个朋友的朋友。

在建立此网络之后，我们想挑选一个调查的样本，也就是说要从网络中选择一组人。由于朋友之间通常拥有相似的兴趣，因此样本不应包含任何一对互为朋友的人。每个人都会有一个调查的可信度，表示为一个正整数，而我们想要找出一个可信度总和最大的样本。

任务

给定各阶段的描述以及每个人的可信度值，请找出一个可信度总和最大的样本。你只需要实现函数 findSample。

• findSample(n, confidence, host, protocol)
  • $n$: 人数.
  • confidence: 大小为 $n$ 的数组；confidence[i]表示第 $i$ 号人的可信度。
  • host: 大小为 $n$ 的数组；host[i] 表示阶段 $i$ 的主持人。
  • protocol: 大小为 $n$ 的数组；protocol[i] 表示在阶段 ($0<i<n$) 所采用的方式的代码: $0$ 代表 IAmYourFriend，$1$ 代表 MyFriendsAreYourFriends，而 $2$ 代表 WeAreYourFriends。
  • 由于在阶段$0$中没有主持人，因此 host[0] 和 protocol[0] 是没有被定义的，而且在你的程序中也不应访问它们。
  • 这个函数应该返回样本可信度总和的最大值。

子任务

有些子任务只会使用其中部分方式，如下表所示。

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现上述的函数，其命名与接口需遵循下面的要求。你还要在该文件中包含头文件friend.h。

int findSample(int n, int confidence[], int host[], int protocol[]);

评测方式

评测系统将会读入如下格式的输入数据：

• 第 $1$ 行: $n$
• 第 $2$ 行: $\text{confidence[0]},\dots ,\text{confidence[n-1]}$
• 第 $3$ 行: $\text{host[1]},\text{protocol[1]},\text{host[2]},\text{protocol[2]},\dots ,\text{host[n-1]},\text{protocol[n-1]}$

评测系统将会输出 findSample 的返回值。

交互式类型的题目怎么本地测试

时间限制：$1\mathtt{\text{s}}$

空间限制：$16\mathtt{\text{MB}}$

下载

样例及测评库下载

什么你说样例1和样例6是相同的？IOI原题也是相同的，不要不服。