113322024-08-16 01:16:16kukkermanFertőzési sorozat (50 pont)cpp17Elfogadva 50/5016ms528 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>

void beolvas(std::istream &be, int &n, std::vector<std::pair<int, int>> &kapcsolatok, std::vector<int> &f_sorozat) {
    int m, k;
    be >> n >> m >> k;

    f_sorozat.resize(k);
    for (auto &x : f_sorozat) {
        be >> x;
    }

    kapcsolatok.resize(m);
    for (auto &x : kapcsolatok) {
        be >> x.first >> x.second;
    }
}

void feldolgoz(int n, const std::vector<std::pair<int, int>> &kapcsolatok, std::vector<int> &f_sorozat) {
    const int k = static_cast<int>(f_sorozat.size());

    if (k == 1) {
        std::cout << n << '\n';
        for (int i = 1; i <= n; i++) {
            std::cout << i << ' ';
        }
        std::cout << '\n';

        return;
    }

    std::vector<std::vector<int>> g(n);
    for (const auto &k : kapcsolatok) {
        g[k.first - 1].push_back(k.second - 1);
        g[k.second - 1].push_back(k.first - 1);
    }

    for (auto &f : f_sorozat) {
        --f;
    }

    std::vector<bool> zero_jelolt(n, true);
    for (int i = 1; i < k; i++) {
        zero_jelolt[f_sorozat[i]] = false;
    }

    std::vector<int> sorrend(n);
    std::vector<int> zero_paciensek;
    for (int p = 0; p < n; p++) {
        if (zero_jelolt[p]) {
            std::vector<bool> lattam(n, false);
            std::vector<int> p_tav(n);
            std::deque<int> sor{ p };
            p_tav[p] = 0;
            lattam[p] = true;

            int i = 0;
            sorrend[i++] = p;
            while (!sor.empty()) {
                const auto akt = sor.front();
                sor.pop_front();

                for (const auto sz : g[akt]) {
                    if (!lattam[sz]) {
                        p_tav[sz] = p_tav[akt] + 1;
                        lattam[sz] = true;
                        sor.push_back(sz);
                        sorrend[i++] = sz;
                    }
                }
            }

            const auto f = find_if(f_sorozat.begin(), f_sorozat.end(), [&](int i) { return p_tav[i] != p_tav[f_sorozat[0]]; }) - f_sorozat.begin();
            const auto s_kezd = find_if(sorrend.begin(), sorrend.end(), [&](int i) { return p_tav[i] > p_tav[f_sorozat[0]]; }) - f;

            if (sorrend.end() - s_kezd >= k && std::equal(f_sorozat.begin(), f_sorozat.end(), s_kezd, [&](int f, int s) { return p_tav[f] == p_tav[s]; })) {
                zero_paciensek.push_back(p);
            }
        }
    }

    std::cout << zero_paciensek.size() << '\n';
    for (auto p : zero_paciensek) {
        std::cout << p + 1 << ' ';
    }
    std::cout << '\n';
}

int main() {
    int n;
    std::vector<std::pair<int, int>> kapcsolatok;
    std::vector<int> f_sorozat;
    beolvas(std::cin, n, kapcsolatok, f_sorozat);

    feldolgoz(n, kapcsolatok, f_sorozat);

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms400 KiB
2Elfogadva0/03ms364 KiB
3Elfogadva0/06ms484 KiB
4Elfogadva2/22ms356 KiB
5Elfogadva2/23ms356 KiB
6Elfogadva2/24ms392 KiB
7Elfogadva2/24ms504 KiB
8Elfogadva2/26ms356 KiB
9Elfogadva2/26ms356 KiB
10Elfogadva2/214ms496 KiB
11Elfogadva1/13ms504 KiB
12Elfogadva2/27ms360 KiB
13Elfogadva2/28ms488 KiB
14Elfogadva2/26ms356 KiB
15Elfogadva2/27ms376 KiB
16Elfogadva2/28ms376 KiB
17Elfogadva2/26ms360 KiB
18Elfogadva1/17ms356 KiB
19Elfogadva1/18ms376 KiB
20Elfogadva1/16ms492 KiB
21Elfogadva1/114ms356 KiB
22Elfogadva1/114ms376 KiB
23Elfogadva1/113ms376 KiB
24Elfogadva1/112ms412 KiB
25Elfogadva1/112ms504 KiB
26Elfogadva1/113ms376 KiB
27Elfogadva1/114ms356 KiB
28Elfogadva1/114ms504 KiB
29Elfogadva1/114ms356 KiB
30Elfogadva1/113ms356 KiB
31Elfogadva1/113ms356 KiB
32Elfogadva1/114ms504 KiB
33Elfogadva1/13ms504 KiB
34Elfogadva1/114ms424 KiB
35Elfogadva1/116ms504 KiB
36Elfogadva1/114ms528 KiB
37Elfogadva1/116ms376 KiB
38Elfogadva1/114ms376 KiB
39Elfogadva1/114ms368 KiB
40Elfogadva1/18ms488 KiB