TLE '17 Contest 3 P3 - Fax's Thanksgiving Dish

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Java 3.0s
Python 3.0s
Memory limit: 256M
Java 512M
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
Is that spaghetti and bok-choi???

Fax McClad, Croneria's most meticulous bounty hunter, is going to prepare a dish for Thanksgiving! Fax prepared a turkey last year, so this year, he will cook something different.

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 will appear at most once as a required item in a recipe, and item 1 will not appear as a required item.

Fax wants to have one unit of item 1 as his dish. For each item i, he currently has Q_i units of that item.

Dankey Kang, Fax's enemy, wants to ruin Fax's Thanksgiving, so he will steal some food items from Fax so that he cannot have item 1. What is the minimum number of items that Dankey Kang must take?


1 \le N \le 300\,000

0 \le M < N

0 \le Q_i \le 7000

SubtaskPointsAdditional Constraints
110There is exactly 1 item, i.e., Q_1+Q_2+\dots+Q_N=1
225Q_i=1 for all 1 \le i \le N
325N \le 15

Input Specification

The first line will contain integers N and M.

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 N integers. The i^{th} integer in this line is Q_i.

Sample Input 1

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

Sample Output 1


Explanation for Sample Output 1

Dankey Kang can steal item 1, item 3, and item 4. Afterwards, Fax cannot have item 1 by following the recipes.

It is not possible to ruin Fax's Thanksgiving by stealing 2 items. For example, if Dankey Kang stole item 1 and item 4, the food list will become 0 2 1 0 3 0 0 10. Fax can follow the second recipe, and then the first recipe, to produce item 1.

Sample Input 2

3 2
2 1 3
3 1 2
0 0 1

Sample Output 2



  • 2
    ryx  commented on Dec. 1, 2017, 10:54 p.m. edited

    The problem is a little unclear. What is the meaning of “each item will appear at most once as a required item in a recipe”? Can a item appear in two recipes? Can there be a cycle, such as item 2 requires item 3 and item 3 also requires item 2?

    • 4
      aeternalis1  commented on Dec. 1, 2017, 11:02 p.m.

      Each item cannot appear in two recipes. Each item will only have at most one recipe, and can only belong to at most one recipe.

      • 1
        ryx  commented on Dec. 1, 2017, 11:53 p.m.

        Can there be a cycle, such as item 2 requires item 3 and item 3 also requires item 2? A cycle seems satisfy all the conditions you mentioned. Thanks

        • 3
          aeternalis1  commented on Dec. 2, 2017, 8:58 a.m.

          If there were to be a cycle, it is evident that it wouldn't have any effect on the final solution, since neither of the cycled ingredients would actually be part of a recipe to create item one, due to the fact that each item can belong to at most one recipe.

          • 2
            ryx  commented on Dec. 2, 2017, 1:20 p.m.

            Thanks a lot. Now I understand that no cycles are reachable from item 1.

        • 0
          P234rex  commented on Dec. 2, 2017, 1:12 a.m. edited

          Edit: In that case, I have no idea what I'm talking about lmao

          • 2
            ryx  commented on Dec. 2, 2017, 1:29 p.m.

            No, it is possible to have cycles, but cycles do not impact the final solution. Please see @aeternalis1 comment. Not sure if system test cases include cycles.