ABC304 C-Virus (C++)

C - Virus

検討

人1の感染者から距離D以内にいる人は感染し、そして感染した人の距離D以内にいる人にまた感染します。人1からの深さ優先探索で解きました。

回答

#include <bits/stdc++.h>
using namespace std;

set<int> searched;

void DFS (vector<vector<int>> &branch, int now) {
    searched.insert(now);

    for (auto b : branch[now]) {
        if (searched.count(b)) continue;
        DFS(branch, b);
    }
}

int main() {
    int N, D; cin >> N >> D;
    vector<pair<int, int>> point(N);
    for (int i = 0; i < N; i++) cin >> point[i].first >> point[i].second;

    vector<vector<int>> B(N);

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int X = point[i].first - point[j].first;
            int Y = point[i].second - point[j].second;

            if ((X * X + Y * Y) <= (D * D)) {
                B[i].emplace_back(j);
                B[j].emplace_back(i);
            }
        }
    }

    DFS(B, 0);

    for (int i = 0; i < N; i++) {
        if (searched.count(i)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

実行時間138msでACでした。