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

Points: 10 (partial)

Time limit: 2.0s

Java 3.0s

Python 3.0s

Memory limit: 256M

Java 512M

Python 512M

Authors:

ZQFMGB12, d

Problem type

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$ ~N~ different food items, numbered from $1$ ~1~ to $N$ ~N~. There are $M$ ~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$ ~1~ will not appear as a required item.

Fax wants to have one unit of item $1$ ~1~ as his dish. For each item $i$ ~i~, he currently has $Q_i$ ~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$ ~1~. What is the minimum number of items that Dankey Kang must take?

Constraints

$1 \le N \le 300\,000$ ~1 \le N \le 300\,000~

$0 \le M < N$ ~0 \le M < N~

$0 \le Q_i \le 7000$ ~0 \le Q_i \le 7000~

Subtask	Points	Additional Constraints
1	10	There is exactly $1$ ~1~ item, i.e., $Q_1+Q_2+\dots+Q_N=1$ ~Q_1+Q_2+\dots+Q_N=1~
2	25	$Q_i=1$ ~Q_i=1~ for all $1 \le i \le N$ ~1 \le i \le N~
3	25	$N \le 15$ ~N \le 15~
4	40	None

Input Specification

The first line will contain integers $N$ ~N~ and $M$ ~M~.

Each of the next $M$ ~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$ ~N~ integers. The $i^\text{th}$ ~i^\text{th}~ integer in this line is $Q_i$ ~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$ ~1~, item $3$ ~3~, and item $4$ ~4~. Afterwards, Fax cannot have item $1$ ~1~ by following the recipes.

It is not possible to ruin Fax's Thanksgiving by stealing $2$ ~2~ items. For example, if Dankey Kang stole item $1$ ~1~ and item $4$ ~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$ ~1~.

Sample Input 2

Sample Output 2

Comments

2

ryx commented on Dec. 2, 2017, 3:54 a.m. ← edit 2 →

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 an 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. 2, 2017, 4:02 a.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. 2, 2017, 4:53 a.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, 1:58 p.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, 6:20 p.m.

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

0

P234rex commented on Dec. 2, 2017, 6: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, 6:29 p.m. ← edited →

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.