C - Virus Editorial by en_translator
Consider a graph with vertices , where there is an undirected edge between vertex and if and only if the distance between and is or less.
Person is infected with the virus if and only if there is a path from vertex to vertex in the graph defined above, i.e. vertex and vertex belongs to the same connected component.
Therefore, we can obtain the correct answer by a graph-searching algorithm such as DFS (Depth-First Search), BFS (Breadth-First Search), or DSU (Disjoint Set Union).
If you use DFS or BFS, the time complexity is because there are vertices and edges; if you use DSU, the complexity is a bit worse, but it is still fast enough.
Sample code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, d;
cin >> n >> d;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
vector<vector<bool>> graph(n, vector<bool>(n));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d) graph[i][j] = true;
vector<bool> ans(n);
ans[0] = true;
queue<int> que; que.push(0);
while (!que.empty()) {
int q = que.front(); que.pop();
for (int i = 0; i < n; i++) {
if (graph[q][i] && !ans[i]) {
ans[i] = true;
que.push(i);
}
}
}
for (int i = 0; i < n; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
}
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int n, d; cin >> n >> d; vector<int> x(n), y(n); for (int i = 0; i < n; i++) cin >> x[i] >> y[i]; vector<vector<bool>> graph(n, vector<bool>(n)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d) graph[i][j] = true; vector<bool> ans(n); ans[0] = true; queue<int> que; que.push(0); while (!que.empty()) { int q = que.front(); que.pop(); for (int i = 0; i < n; i++) { if (graph[q][i] && !ans[i]) { ans[i] = true; que.push(i); } } } for (int i = 0; i < n; i++) cout << (ans[i] ? "Yes" : "No") << '\n'; }
posted:
last update: