TLE '17 Contest 4 P3 - Fax's Christmas Dish

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Python 3.0s
Memory limit: 256M
Python 512M

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
Presentation could be improved, but it was pretty tasty!

Fax McClad, Croneria's most meticulous bounty hunter, is going to prepare a dish for Christmas!

There are N different food items, numbered from 1 to N. There are M different recipes. A recipe consists of a non-empty list of items that need to be combined to produce a target item. Only one unit of each item in the list is required, and the target item will not be in the list. Additionally, no two recipes will have the same target item, each item in the list has a greater number than the target item's number, item 1 is the target item in exactly one recipe, and items 2 to N appear in exactly one recipe's list.

Fax wants to have one unit of item 1 as his dish. He will receive 1 item on each of the next D days. On the i^{th} day, he will receive item P_i.

What is the earliest day that Fax can obtain item 1?


2 \le N \le 300\,000

1 \le M < N

1 \le D \le 300\,000

1 \le P_i \le N

SubtaskPointsAdditional Constraints
330N,D \le 2000

Input Specification

The first line will contain integers N, M, and D.

Each of the next M lines will contain one recipe. A recipe is one line long and follows this format:

  • The first integer is the target item.
  • The second integer is the number of required items.
  • The remaining integers are the required items.

The last line will contain D integers. The i^{th} integer in this line is P_i.

Output Specification

If Fax cannot obtain item 1 after all D days, output -1. Otherwise, output the earliest day that Fax can obtain item 1.

Sample Input 1

7 3 8
2 2 3 6
4 2 5 7
1 2 2 4
3 3 6 3 5 4 4 1

Sample Output 1


Explanation for Sample Output 1

After 6 days, Fax has these items: 3 3 6 3 5 4. Fax can follow the first recipe to get 2 3 3 5 4, then the third recipe to get 1 3 3 5.

Sample Input 2

4 1 7
1 3 2 3 4
2 2 3 3 2 3 3

Sample Output 2



  • 0
    max  commented on Oct. 2, 2018, 4:03 a.m. edited

    What is the upper bound of M?

    Edit: I just saw this 9 months later... either I couldn't read, or the problem statement has since been updated.