codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

350B.md (2693B)


      1 Source: https://codeforces.com/problemset/problem/350/B
      2 
      3 B. Resort
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Valera's finally decided to go on holiday! He packed up and headed for a ski resort.
     22 
     23 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.
     24 
     25 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.
     26 
     27 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:
     28 
     29 1. Objects with numbers *v*1, *v*2, ..., *v**k* - 1 are mountains and the object with number *v**k* is the hotel.
     30 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.
     31 3. The path contains as many objects as possible (*k* is maximal).
     32 
     33 Help Valera. Find such path that meets all the criteria of our hero!
     34 
     35 Input
     36 
     37 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the number of objects.
     38 
     39 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.
     40 
     41 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*.
     42 
     43 Output
     44 
     45 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.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 5  
     53 0 0 0 0 1  
     54 0 1 2 3 4
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 5  
     61 1 2 3 4 5
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 5  
     68 0 0 1 0 1  
     69 0 1 2 2 4
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 2  
     76 4 5
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 4  
     83 1 0 0 0  
     84 2 3 4 2
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 1  
     91 1
     92 ```