시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 30 | 13 | 9 | 42.857% |
Rikka and her classmates are playing an online game. There are $n$ players in the game, and there are some pairs of friend relationships among players. The friend relationship is bidirectional.
At the beginning of the game, one player is selected as "dragon" randomly, and other players are marked as "hero".
The game proceeds in turns. Each turn contains the following three steps:
When the game ends, each alive "hero" will gain $10$ points, the last "dragon" will get $100$ points and each eliminated player will gain only $1$ point.
All players want to maximize his/her points, and suppose all players are clever enough.
For each player, Rikka wants you to determine: If this player is selected as the "dragon" at the beginning, whether the game will end immediately in the first turn?
The first line contains a single integer $n\ (1 \leq n \leq 500)$, representing the number of players.
Then $n$ lines follow. Each line contains an $01$-string $s_i$ of length $n$. $s_{i,j}=1$ if and only if player $i$ and player $j$ are friends.
The input guarantees that $s_{i,j} = s_{j,i}$ and $s_{i,i}=0$.
Output a single line with a $01$-string $res$ of length $n$. $res_i = 1$ if and only if the game will end immediately in the first turn if player $i$ is selected as the first "dragon".
2 00 00
00
3 000 000 000
111
4 0111 1000 1000 1000
1111
4 0101 1010 0101 1010
0000
For the first sample, whatever which player is selected, the other player will choose to attack: He/she will get $100$ points if he chooses to attack, otherwise, he/she can get only $10$ points. Therefore, the game continues to the second turn.
For the second sample, without loss of the generality, suppose the third player is selected as the first "dragon". Then:
Therefore, the game will end in the first turn.