P9052 [PA 2021] Arenas

Bajtek received the newest computer game Byte Defence 4 from his parents for Christmas. He excitedly launched the game and started playing. The character he controls is called Bajtonator, who becomes stronger by fighting monsters, completing quests, and upgrading equipment. There are $n$ special arenas on the map, which contain very rare loot. However, there are also $n$ types of passes, and to enter an arena you must have the corresponding pass. The rules of the game are as follows: 1. If you have the pass for an arena, you can enter that arena and fight monsters. Entering an arena does not consume the pass. Monsters revive after you leave, so the same pass can be used repeatedly to challenge the same arena. 2. Each arena has a pre-announced, fixed pass pool, and the passes in the pool are never removed or changed. After defeating the monsters in an arena, besides possibly dropping rare items, the game will randomly pick one pass from that arena’s pass pool, make a copy, and give it to you. Therefore, after many victories, you may own multiple copies of the same type of pass. After reading a guide, Bajtek learned that arenas with larger indices are harder. His strength can be represented by an integer $k$: he will certainly win in any arena with index $\le k$, and he will certainly lose in any arena with index $> k$. At the beginning, he has no passes and can only spend money to buy **one**. Which one is the best to buy? He believes that if he buys the pass for arena $A$, then using this initial pass and the passes obtained from battles afterward, **no matter what**, he will eventually be able to enter arena $B$ and win. In that case, this pass is worth buying. So he wants to know, for a fixed $k$, how many ordered pairs of arenas $(A,B)$ satisfy: 1. $A \ne B$. 2. If he buys only the pass for arena $A$, then using this initial pass and the passes obtained from battles afterward, no matter what, he will eventually be able to enter arena $B$ and win. You need to compute the number of such ordered pairs $(A,B)$ for $k = 1,2,\cdots,n$.

The first line contains an integer $n\;(2\le n\le 2\cdot 10^5)$, the number of arenas. The next $n$ lines describe the pass pools. In the $i$-th line, the first integer is $l_i\;(1\le l_i)$, the size of the pass pool of arena $i$. Then follow $l_i$ integers, each denoting the arena index that the corresponding pass allows you to enter. The sum of all $l_i$ does not exceed $5\cdot10^5$.

One line with $n$ integers, where the $i$-th integer is the answer when $k = i$.

Translated by ChatGPT 5