| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 (추가 시간 없음) | 1024 MB | 3488 | 1530 | 1100 | 42.702% |
당신은 루머를 믿는가?
한 유명 심리학 실험에서는 사람들에게 두 개의 줄을 보여주고, 어떤 줄이 더 긴지 말하라 했다. 사실 한 사람을 제외하고 나머지는 실험자에 의해 사전에 조작된 사람들이었다. 조작된 사람들은 사실상 더 짧은 줄을 더 길다고 말했다. 주변 모두가 같은 답변을 하자, 진짜 피실험자 또한 짧은 줄이 더 길다고 말했다. 이 실험은 사람들이 주변인의 영향을 강하게 받는다는 것을 보여주었는데, 루머도 이와 같다.
루머는 최초 유포자로부터 시작한다. 최초 유포자는 여러 명일 수 있고, 최초 유포자를 제외하고 스스로 루머를 만들어 믿는 사람은 없다.
매분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트리며, 군중 속 사람은 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다.
루머를 믿는 순간부터 다른 말은 듣지 않기 때문에, 한번 믿은 루머는 계속 믿는다.
이때, 사람들이 루머를 처음 믿기 시작하는 시간을 알아내 보자.
첫째 줄에 사람의 수 $N$이 주어진다. (1ドル \leq N \leq 200\ 000$) 이는 1ドル$번 사람부터 $N$번 사람까지 있음을 의미한다.
둘째 줄부터 $N$개의 줄이 주어진다. 이 중 $i(1 \leq i \leq N)$번째 줄에는 $i$번 사람의 주변인들의 번호와 입력의 마지막을 나타내는 0이 공백으로 구분되어 주어진다. 번호는 1ドル$ 이상 $N$ 이하의 자연수이고, 같은 줄에 중복된 번호는 없다. 자기 자신이 주변인이거나 일방적으로 주변인인 경우는 없으며, 전체 양방향 주변인 관계는 1ドル\ 000\ 000$개를 넘지 않는다.
다음 줄에는 루머를 퍼뜨리는 최초 유포자의 수 $M$이 주어진다. $(1 \leq M \leq N)$
마지막 줄에는 최초 유포자의 번호가 공백으로 구분되어 주어진다. 최초 유포자의 번호는 중복되지 않는다.
$N$개의 정수 $t_1,t_2,\cdots,t_N$을 공백 단위로 출력한다. $t_i$는 $i$번 사람이 루머를 처음 믿기 시작한 시간(분)이며, 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 $-1$이다. 최초 유포자는 루머를 0ドル$분부터 믿기 시작했다고 생각한다.
7 2 3 0 1 3 0 1 2 4 0 3 5 0 4 0 0 0 2 1 6
0 1 2 3 4 0 -1
7 2 4 0 1 3 0 2 5 0 1 5 6 0 3 4 6 7 0 4 5 7 0 5 6 0 1 6
4 4 3 3 2 0 1
예제 1
0분 : 최초 유포자(1ドル,ドル 6ドル$번 사람)가 루머를 생성한다.
1분 : 1ドル$번 사람은 2ドル,ドル 3ドル$번 사람에게 루머를 퍼뜨린다. 2ドル$번 사람은 주변인 2ドル$명 중 1ドル$명이 루머를 믿고 있어 루머를 믿게 된다. 3ドル$번 사람은 주변인 3ドル$명 중 1ドル$명만 루머를 믿기 때문에, 루머를 믿지 않는다. 6ドル$번 사람은 루머를 퍼뜨릴 주변인이 없다.
2분 : 1ドル,ドル 2ドル$번 사람은 3ドル$번 사람에게 루머를 퍼뜨린다. 인접한 3ドル$명 중 절반 이상인 2ドル$명이 루머를 믿고 있어, 3ドル$번 사람도 2ドル$분부터 믿기 시작한다.
3분 : 3ドル$번 사람은 4ドル$번 사람에게 루머를 퍼뜨린다. 4ドル$번 사람이 믿기 시작한다.
4분 : 5ドル$번 사람도 루머를 믿게 된다. 7ドル$번 사람은 이후 충분한 시간이 지나도 루머를 믿지 않는다.