|Codeforces Round #728 (Div. 1)|
Note that the memory limit is unusual.
There are $$$n$$$ chefs numbered $$$1, 2, \ldots, n$$$ that must prepare dishes for a king. Chef $$$i$$$ has skill $$$i$$$ and initially has a dish of tastiness $$$a_i$$$ where $$$|a_i| \leq i$$$. Each chef has a list of other chefs that he is allowed to copy from. To stop chefs from learning bad habits, the king makes sure that chef $$$i$$$ can only copy from chefs of larger skill.
There are a sequence of days that pass during which the chefs can work on their dish. During each day, there are two stages during which a chef can change the tastiness of their dish.
All chefs work to maximize the tastiness of their own dish in order to please the king.
Finally, you are given $$$q$$$ queries. Each query is one of two types.
Note that queries of type $$$1$$$ are independent of each all other queries. Specifically, each query of type $$$1$$$ is a scenario and does not change the initial tastiness $$$a_i$$$ of any dish for future queries. Note that queries of type $$$2$$$ are cumulative and only change the initial tastiness $$$a_i$$$ of a dish. See notes for an example of queries.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 300$$$) — the number of chefs.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-i \le a_i \le i$$$).
The next $$$n$$$ lines each begin with a integer $$$c_i$$$ ($$$0 \le c_i < n$$$), denoting the number of chefs the $$$i$$$-th chef can copy from. This number is followed by $$$c_i$$$ distinct integers $$$d$$$ ($$$i < d \le n$$$), signifying that chef $$$i$$$ is allowed to copy from chef $$$d$$$ during stage $$$2$$$ of each day.
The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.
Each of the next $$$q$$$ lines contains a query of one of two types:
It is guaranteed that there is at least one query of the first type.
For each query of the first type, print a single integer — the answer to the query.
5 1 0 -2 -2 4 4 2 3 4 5 1 3 1 4 1 5 0 7 1 1 1 5 2 4 3 1 1 1 5 2 3 2 1 2 2 4 2 5 1 1 981 4 5
57 71 316 278497818
Below is the set of chefs that each chef is allowed to copy from:
Following is a description of the sample.
For the first query of type $$$1$$$, the initial tastiness values are $$$[1, 0, -2, -2, 4]$$$.
The final result of the first day is shown below:
So, the answer for the $$$1$$$-st query is $$$21 + 0 - 2 + 18 + 20 = 57$$$.
For the $$$5$$$-th query ($$$3$$$-rd of type $$$1$$$). The initial tastiness values are now $$$[1, 0, 0, 1, 4]$$$.
So, the answer for the $$$5$$$-th query is $$$12+108+196=316$$$.
It can be shown that, in each step we described, all chefs moved optimally.