Algorithm/BOJ
UCPC 2020 예선 G / 루머 - 19538
jhg0406
2020. 8. 5. 21:38
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
queue<int> black[2];
vector<vector<int>> adj, blackAdj;
vector<bool> isWhite;
vector<int> ans;
void linkBk(int here) {
for(int i = 0; i<adj[here].size(); ++i) {
int there = adj[here][i];
blackAdj[there].push_back(here);
}
}
void update(queue<int>& tmp) {
while(!tmp.empty()) {
int u = tmp.front();
tmp.pop();
linkBk(u);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
black[0] = black[1] = queue<int>();
blackAdj = adj = vector<vector<int>>(N+1);
isWhite = vector<bool>(N+1, true);
ans = vector<int>(N+1, -1);
for(int i = 1; i<=N; ++i) {
int j;
while(true) {
cin >> j;
if(!j) break;
adj[i].push_back(j);
adj[j].push_back(i);
}
}
cin >> M;
int q;
for(int i = 0; i<M; ++i) {
cin >> q;
black[1].push(q);
isWhite[q] = false;
ans[q] = 0;
linkBk(q);
}
int iter = 1;
while(true) {
queue<int> tmp;
while(!black[iter%2].empty()) {
int here = black[iter%2].front();
black[iter%2].pop();
for(int i = 0; i<adj[here].size(); ++i) {
int there = adj[here][i];
if(!isWhite[there]) continue;
int aBN = blackAdj[there].size();
int aAN = adj[there].size();
if(aBN + aBN >= aAN) {
isWhite[there] = false;
black[(iter+1)%2].push(there);
ans[there] = iter;
tmp.push(there);
}
}
}
if(!tmp.size()) break;
update(tmp);
++iter;
}
for(int i = 1; i<=N; ++i)
cout << ans[i] << " ";
}
|
cs |
https://www.acmicpc.net/problem/19538
19538번: 루머
예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$�
www.acmicpc.net
루머
이번 타임에 루머를 믿게 되는 사람들은, 모두 바로 직전타임에 루머를 믿게된 사람의 인접한 사람들입니다.
위의 아이디어를 이용해 BFS탐색을 돌려주면 됩니다.
