Official

C - Virus Editorial by en_translator


Consider a graph with NN vertices 1,2,,N1,2, \ldots, N, where there is an undirected edge between vertex ii and jj if and only if the distance between (Xi,Yi)(X_i,Y_i) and (Xj,Yj)(X_j,Y_j) is DD or less.

Person ii is infected with the virus if and only if there is a path from vertex 11 to vertex ii in the graph defined above, i.e. vertex 11 and vertex ii 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 O(N2)O(N^2) because there are NN vertices and O(N2)O(N^2) edges; if you use DSU, the complexity is a bit worse, but it is still fast enough.

Sample code

Copy
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. int main() {
  6. int n, d;
  7. cin >> n >> d;
  8. vector<int> x(n), y(n);
  9. for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
  10. vector<vector<bool>> graph(n, vector<bool>(n));
  11. 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;
  12. vector<bool> ans(n);
  13. ans[0] = true;
  14. queue<int> que; que.push(0);
  15. while (!que.empty()) {
  16. int q = que.front(); que.pop();
  17. for (int i = 0; i < n; i++) {
  18. if (graph[q][i] && !ans[i]) {
  19. ans[i] = true;
  20. que.push(i);
  21. }
  22. }
  23. }
  24. for (int i = 0; i < n; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
  25. }
#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:



2025-04-09 (Wed)
16:11:22 +00:00