409617: GYM103643 T Revert to Zero

Like most members of the JoJo bloodline, you've been bestowed a unique, miraculous ability. Your ability allows you to revert your enemy's actions to zero! You're currently battling a tough enemy.

Your enemy can be represented by a directed graph. Nodes represent actions and each action has an effect. The effect of the $$$i$$$th action is $$$E_i$$$ $$$(1 \leq E_i \leq 10^5)$$$. There is an edge from action $$$u$$$ to action $$$v$$$ if $$$u$$$ influences $$$v$$$. At first, your enemy has $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ actions labeled from $$$1 \dots N$$$. Action $$$1$$$ influences actions $$$2 \dots N$$$.

Actions $$$2 \dots N$$$ are called foundational actions. Denote $$$foundation(x)$$$ as the set of foundational actions such there exists a path from each action to $$$x$$$. In particular, $$$foundation(1) = \{\}$$$ (the empty set) and $$$foundation(i) = \{i\}$$$ for all $$$i$$$ such that $$$2 \leq i \leq N$$$.

During your fight, $$$M$$$ $$$(1 \leq M \leq 10^5)$$$ events of $$$2$$$ types occur. The type of the $$$i$$$th event is $$$T_i$$$.

If $$$T_i = 1$$$, your enemy creates a new action $$$a_i$$$, where $$$a_i$$$ is the number of actions after creating $$$a_i$$$. $$$a_i$$$ is influenced by $$$K_i$$$ distinct actions, $$$B_{1,\, i}, B_{2,\, i}, \dots B_{K_i,\, i}$$$ $$$(1 \leq B_{j,\, i} \lt a_i)$$$. The sum of $$$K_i$$$ over all $$$i$$$ is $$$\leq 10^6$$$. It's guaranteed that $$$foundation(j) \neq foundation(a_i)$$$ for any action $$$j \neq a_i$$$. It's also guaranteed that for any proper subset $$$s$$$ of $$$foundation(a_i)$$$ (including the empty set), $$$s = foundation(B_{j,\, i})$$$ for some $$$j$$$ . Finally, it's also guaranteed that for any $$$j$$$, $$$foundation(B_{j,\, i}) = s$$$ for some proper subset $$$s$$$ of $$$foundation(a_i)$$$.

If $$$T_i = 2$$$, your enemy changes the effect of action $$$1$$$ to $$$C_i$$$ $$$(1 \leq C_i \leq 10^5)$$$. Then, you need to figure out the minimum total effort needed to revert your enemy's actions to zero (make $$$E_j = 0$$$ for all $$$j$$$). To use your ability, select an action $$$j$$$ that you have not selected before and an integer $$$x$$$ ($$$x$$$ can be negative). Then, add $$$x$$$ to the effect of $$$j$$$ and the effects of all actions $$$j$$$ influences. This takes $$$3 \cdot x^3 + 2 \cdot x^2 + x$$$ effort. You may use your ability any number of times. Your total effort is the sum of each effort. Note that you only find the minimum total effort and do not change any $$$E_j$$$.

The first line contains $$$2$$$ integers, $$$N$$$, $$$M$$$.

The second line contains $$$N$$$ integers, $$$E_1, E_2, \dots, E_N$$$.

The next $$$M$$$ lines describe the events, one event per line. The first integer of the $$$i$$$th line is $$$T_i$$$. If $$$T_i = 1$$$, then $$$E_{A_i}$$$, $$$K_i$$$, and $$$B_{1,\, i}, B_{2,\, i}, \dots, B_{K_i,\, i}$$$ follow. If $$$T_i = 2$$$, then $$$C_i$$$ follows.

For each event of type $$$2$$$, print the minimum total effort needed to revert your enemy's actions to zero$$$\mod 10^9 + 7$$$ on a separate line.

3 2
3 1 2
1 1 3 1 3 2
2 1

2

For the example, your enemy starts with $$$3$$$ actions and there are $$$2$$$ events. Action $$$1$$$ has effect $$$3$$$, action $$$2$$$ has effect $$$1$$$, and action $$$3$$$ has effect $$$2$$$. Action $$$1$$$ influences actions $$$2$$$ and $$$3$$$, which are foundational actions.

$$$---------------------------------------------$$$

Since the $$$1$$$st event is of type $$$1$$$, your enemy creates an action. Action $$$4$$$ is created with effect $$$1$$$, and it is influenced by actions $$$1$$$, $$$3$$$, and $$$2$$$. $$$foundation(4) = \{2, 3\}$$$, $$$foundation(B_{1,\, 1}) = foundation(1) = \{\}$$$, $$$foundation(B_{2,\, 1}) = foundation(3) = {3}$$$, and $$$foundation(B_{3,\, 1}) = foundation(2) = \{2\}$$$.

Thus, for any proper subset $$$s$$$ of $$$foundation(4) =$$$ $$$\{\}$$$, $$$\{2\}$$$, or $$$\{3\}$$$, $$$s = foundation(B_{j,\, 1})$$$ for some $$$j =$$$ $$$1$$$, $$$2$$$, or $$$3$$$. Furthermore, for any $$$j =$$$ $$$1$$$, $$$2$$$, or $$$3$$$, $$$foundation(B_{j,\, 1}) = s$$$ for some proper subset $$$s$$$ of $$$foundation(4) =$$$ $$$\{\}$$$, $$$\{2\}$$$, or $$$\{3\}$$$.

$$$---------------------------------------------$$$

Since the $$$2$$$nd event is of type $$$2$$$, you need to find the minimum total effort needed to revert your enemy's actions to zero. Your enemy changes the effect of action $$$1$$$ to $$$1$$$. Here's one way to achieve the minimum effort:

Right now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[1,\, 1,\, 2,\, 1]$$$.

Use your ability on action $$$3$$$ and choose $$$x = -1$$$. This takes $$$3\cdot{(-1)}^3 + 2\cdot{(-1)}^2 -1 = -2$$$ effort. Now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[1,\, 1,\, 1,\, 0]$$$.

Then, use your ability on action $$$1$$$ and choose $$$x = -1$$$. This takes $$$3\cdot{(-1)}^3 + 2\cdot{(-1)}^2 -1 = -2$$$ effort. Now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[0,\, 0,\, 0,\, -1]$$$.

Finally, use your ability on action $$$4$$$ and choose $$$x = 1$$$. This takes $$$3\cdot1^3 + 2\cdot1^2 + 1 = 6$$$ effort. Now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[0,\, 0,\, 0,\, 0]$$$, so you've successfully reverted your enemy's actions to zero.

$$$---------------------------------------------$$$

In total, you took $$$-2 -2 + 6 = 2$$$ effort.

$$$---------------------------------------------$$$

Problem Idea: codicon

Problem Preparation: codicon

Occurrences: Advanced 13