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:

  1. Objects with numbers _v_1, _v_2, ..., v__k - 1 are mountains and the object with number v__k is the hotel.
  2. 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.
  3. The path contains as many objects as possible (k is maximal).

Help Valera. Find such path that meets all the criteria of our hero!

瓦莱拉终于决定去度假了!他收拾好行装,前往一座滑雪场。

瓦莱拉本想来一次滑雪之旅,但他很快意识到自己可能会在这个新地方迷路。有人给了他一个有用的提示:该滑雪场共有 nn 个地点(我们将这些地点按某种方式用 11 到 nn 的整数编号),每个地点要么是酒店,要么是山峰。

瓦莱拉还了解到,滑雪场内修建了多条滑雪道。具体来说,对每个地点 vv,滑雪场至多存在一个地点 uu,使得有一条从 uu 到 vv 的滑雪道。此外,我们还知道:没有任何酒店作为滑雪道的起点(即不存在从某家酒店出发指向其他地点的滑雪道)。

瓦莱拉担心自己在滑雪场中迷路,因此希望你为他规划一条行走路径。该路径需由一系列地点 v1, v2, …, vkv_1,\,v_2,\,\dots,\,v_k(其中 k≥1k\geq 1)构成,并满足以下条件:

  1. 编号为 v1, v2, …, vk−1v_1,\,v_2,\,\dots,\,v_{k-1} 的地点均为山峰,而编号为 vkv_k 的地点为酒店;
  2. 对任意整数 ii(1≤i<k1\leq i < k),地点 viv_i 恰好有一条向外延伸的滑雪道,且该滑雪道通向地点 vi+1v_{i+1};
  3. 路径所含地点数量尽可能多(即 kk 取最大值)。

请帮助瓦莱拉!找出一条满足上述所有条件的路径!

输入格式

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测评打分。不知道怎么写?

首页