CF350B.Resort
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Valera's finally decided to go on holiday! He packed up and headed for a ski resort.
Valera's fancied a ski trip but he soon realized that he could get lost in this new place. Somebody gave him a useful hint: the resort has n objects (we will consider the objects indexed in some way by integers from 1 to n), each object is either a hotel or a mountain.
Valera has also found out that the ski resort had multiple ski tracks. Specifically, for each object v, the resort has at most one object u, such that there is a ski track built from object u to object v. We also know that no hotel has got a ski track leading from the hotel to some object.
Valera is afraid of getting lost on the resort. So he wants you to come up with a path he would walk along. The path must consist of objects _v_1, _v_2, ..., v__k (k ≥ 1) and meet the following conditions:
- Objects with numbers _v_1, _v_2, ..., v__k - 1 are mountains and the object with number v__k is the hotel.
- For any integer i (1 ≤ i < k), there is exactly one ski track leading from object v__i. This track goes to object v__i + 1.
- The path contains as many objects as possible (k is maximal).
Help Valera. Find such path that meets all the criteria of our hero!
瓦莱拉终于决定去度假了!他收拾好行装,前往一座滑雪场。
瓦莱拉本想来一次滑雪之旅,但他很快意识到自己可能会在这个新地方迷路。有人给了他一个有用的提示:该滑雪场共有 n 个地点(我们将这些地点按某种方式用 1 到 n 的整数编号),每个地点要么是酒店,要么是山峰。
瓦莱拉还了解到,滑雪场内修建了多条滑雪道。具体来说,对每个地点 v,滑雪场至多存在一个地点 u,使得有一条从 u 到 v 的滑雪道。此外,我们还知道:没有任何酒店作为滑雪道的起点(即不存在从某家酒店出发指向其他地点的滑雪道)。
瓦莱拉担心自己在滑雪场中迷路,因此希望你为他规划一条行走路径。该路径需由一系列地点 v1,v2,…,vk(其中 k≥1)构成,并满足以下条件:
- 编号为 v1,v2,…,vk−1 的地点均为山峰,而编号为 vk 的地点为酒店;
- 对任意整数 i(1≤i<k),地点 vi 恰好有一条向外延伸的滑雪道,且该滑雪道通向地点 vi+1;
- 路径所含地点数量尽可能多(即 k 取最大值)。
请帮助瓦莱拉!找出一条满足上述所有条件的路径!
输入格式
The first line contains integer n (1 ≤ n ≤ 105) — the number of objects.
The second line contains n space-separated integers _type_1, _type_2, ..., type__n — the types of the objects. If type__i equals zero, then the i-th object is the mountain. If type__i equals one, then the i-th object is the hotel. It is guaranteed that at least one object is a hotel.
The third line of the input contains n space-separated integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ n) — the description of the ski tracks. If number a__i equals zero, then there is no such object v, that has a ski track built from v to i. If number a__i doesn't equal zero, that means that there is a track built from object a__i to object i.
第一行包含一个整数 $ n ( 1 \leq n \leq 10^5 $)—— 表示物体的数量。
第二行包含 $ n $ 个用空格分隔的整数 $ \text{type}_1,\ \text{type}_2,\ \dots,\ \text{type}_n $ —— 表示各物体的类型。若 $ \text{type}_i = 0 $,则第 $ i $ 个物体是山;若 $ \text{type}_i = 1 $,则第 $ i $ 个物体是酒店。保证至少有一个物体是酒店。
输入的第三行包含 $ n $ 个用空格分隔的整数 $ a_1,\ a_2,\ \dots,\ a_n ( 0 \leq a_i \leq n $)—— 描述滑雪轨道。若 $ a_i = 0 $,则不存在物体 $ v $,使得从 $ v $ 到 $ i $ 建有一条滑雪轨道;若 $ a_i \neq 0 $,则表示从物体 $ a_i $ 到物体 $ i $ 建有一条滑雪轨道。
输出格式
In the first line print k — the maximum possible path length for Valera. In the second line print k integers _v_1, _v_2, ..., v__k — the path. If there are multiple solutions, you can print any of them.
第一行输出 k —— Valera 能够达到的最大路径长度。
第二行输出 k 个整数 _v_₁, _v_₂, ..., v__k —— 该路径。若存在多种解,输出任意一种即可。
输入输出样例
输入#1
5 0 0 0 0 1 0 1 2 3 4
输出#1
5 1 2 3 4 5
输入#2
5 0 0 1 0 1 0 1 2 2 4
输出#2
2 4 5
输入#3
4 1 0 0 0 2 3 4 2
输出#3
1 1
输入解题思路,AI测评打分。不知道怎么写?