Yet Another Contest 8 P3 - Herobrine

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Java 5.0s
Python 5.0s
Memory limit: 1G

Problem types

Andy is addicted to Minecraft. One day, he decides to download a new mod to enhance his gaming experience. The mod adds a million types of ores into the game, numbered from 1 to 10^6, and requires a subset X of distinct ores to be chosen. The mod then provides two new crafting recipes:

  1. Combine one ore of each type in X, and summon a Herobrine with power |X|, where |X| denotes the size of subset X.
  2. Combine two Herobrines with powers A and B into a single Herobrine with power A + B.

Note that ingredients are destroyed once they are combined in a recipe.

Andy has to mine for these ores. The mine currently consists of N chambers labelled from 1 to N, and N tunnels labelled from 1 to N. The i-th chamber consists of M_i ores which Andy can mine, O_{i,1}, O_{i,2}, \dots, O_{i,M_i}. The i-th tunnel connects chambers P_i and i (P_i < i), with the outside being considered as chamber 0.

Andy decides to begin mining in chamber C. Overhearing his plans, Josh decides to block the C-th tunnel with bedrock. Andy's only chance to escape is to summon a Herobrine to break the bedrock. Therefore, Andy decides to collect all the ores from chambers reachable from chamber C via unblocked tunnels, and to create a single Herobrine with the maximum possible power.

Mike would like to know the power of Andy's Herobrine, but as he is currently looting a village, he has no idea which chamber Andy is in. Therefore, he wants to know: for each value of C between 1 and N, across all possible subsets X, what is the maximum possible power of Andy's Herobrine? Note that X may differ for different values of C.


1 \le N \le 10 ^ 6

0 \le M_i \le 2 \times 10 ^ 6

1 \le \sum\limits_{i=1}^{N} M_i \le 2 \times 10 ^ 6

1 \le O_{i,j} \le 10^6

0 \le P_i < i for all i

Subtask 1 [20%]

1 \le N \le 1000

1 \le M_i \le 2000

1 \le \sum\limits_{i=1}^{N} M_i \le 2000

Subtask 2 [40%]

P_i = i - 1 for all i.

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains one integer, N.

The second line contains N integers, P_1, P_2, \dots, P_N.

The i-th of the following N lines contains one integer, M_i, followed by M_i integers, O_{i,1}, O_{i, 2}, \dots, O_{i,M_i}.

Output Specification

Output N lines. The i-th line should contain one integer, denoting the maximum possible power of Andy's Herobrine if C = i.

Sample Input

0 1 2 2 3 3
4 1 1 2 2
3 1 2 3
2 2 3
2 1 3
4 1 2 3 4
3 1 3 4

Sample Output



Suppose C = 2, so that the second tunnel which connects chambers 1 and 2 is blocked with bedrock. Then, Andy can reach all chambers except chamber 1.

In total, Andy can mine 4 ores of type 1, 3 ores of type 2, 5 ores of type 3, and 2 ores of type 4.

If he chooses X = \{1, 2, 3\}, then he can create 3 Herobrines of power 3 using the first crafting recipe. Using the second crafting recipe, he can combine two Herobrines to form a Herobrine with power 3 + 3 = 6. Using the second crafting recipe again, he can combine the two remaining Herobrines to form a single Herobrine with power 3 + 6 = 9. It can be shown that this choice of X and this sequence of crafting operations is optimal.


There are no comments at the moment.