## CCC '18 J5 - Choose your own path

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Canadian Computing Competition: 2018 Stage 1, Junior #5

There is a genre of fiction called choose your own adventure books. These books allow the reader to make choices for the characters which alters the outcome of the story.

For example, after reading the first page of a book, the reader may be asked a choice, such as "Do you pick up the rock?" If the reader answers "yes", they are directed to continue reading on page , and if they choose "no", they are directed to continue reading on page . On each of those pages, they have further choices, and so on, throughout the book. Some pages do not have any choices, and thus these are the "ending" pages of that version of the story. There may be many such ending pages in the book, some of which are good (e.g., the hero finds treasure) and others which are not (e.g., the hero finds a leftover sandwich from 2001).

You are the editor of one of these books, and you must examine two features of the choose your own adventure book:

1. ensure that every page can be reached – otherwise, there is no reason to pay to print a page which no one can ever read;
2. find the shortest path, so that readers will know what the shortest amount of time they need to finish one version of the story.

Given a description of the book, examine these two features.

#### Input Specification

The first line of input contains , the number of pages in the book. Each of the next lines contain an integer , which is the number of different options from page , followed by space-separated integers in the range from to , corresponding to each of the pages to go to next from page . It will also be the case is at most .

If , then page is an ending page (i.e., there are no choices from that page). There will be at least one ending page in the book.

Note that you always begin the book on page .

For of the available marks, , for .

For an additional of the available marks, the book is guaranteed to have no cycles.

For an additional of the available marks, , for .

#### Output Specification

The output will be two lines. The first line will contain Y if all pages are reachable, and N otherwise.

The last line will contain a non-negative integer , which is the shortest path a reader can take while reading this book. There will always be a finite shortest path.

#### Sample Input 1

3
2 2 3
0
0

#### Sample Output 1

Y
2

#### Explanation for Sample Output 1

Since we start on page , and can reach both page and page , all pages are reachable. The only paths in the book are and , each of which is pages in length.

#### Sample Input 2

3
2 2 3
0
1 1

#### Sample Output 2

Y
2

#### Explanation for Sample Output 2

Every page is reachable, since from page , we can reach pages and . The shortest path is the path , which contains two pages.

• commented on Aug. 26, 2020, 3:40 p.m. edit 2

I've been stuck on this problem for quite a while now... I am just not sure how to implement the shortest path part of this problem... Can someone please help? Thanks.

I kinda solved it? I used Dijkstra but for the odd test case it is failing... My submission is at https://dmoj.ca/submission/2986907. Thanks!

Thanks everyone. I solved it. I was just mishandling the input... I included the first number on each page line (supposed to represent the number of pages you can access) as a page you can access, causing this issue.

• commented on Jan. 21, 2020, 8:37 a.m.

I keep getting RTE on the last batch. Can someone see what's wrong with my code? https://dmoj.ca/src/1834183

• commented on Jan. 21, 2020, 8:34 p.m. edit 4

a vector of N^2 ints, where N <= 10,000, can be up to 4e8 bytes of memory + a bit extra, which is far beyond the stack space that you have available, and in fact larger than the memory limit of the problem.

Declare large data structures globally (see the tips section of About, at the top). That being said, your vector will never need to get that big.

• commented on Jan. 22, 2020, 4:50 p.m.

I figured it out, thanks for the help!

• commented on Jan. 21, 2020, 9:26 p.m.

I also want to add that vector elements are allocated on the heap, regardless of whether it is declared in or out of the main function. The allocation tip only applies to arrays.

• commented on Jan. 21, 2020, 6:24 p.m.

Why do you resize the vector to n*n? I think n+1 suffices.

• commented on July 30, 2018, 8:15 p.m.

The second one is an endless recursion loop between one and three!!!!! >:(

• commented on Aug. 29, 2018, 10:13 a.m.

If you are lazy and you don't want to check the endless loop, you can try Dijkstra instead of bfs to solve this problem😂! To my surprise my code didn't TLE...