113312024-08-16 00:11:00kukkermanFertőzési sorozat (50 pont)cpp17Accepted 50/50216ms1552 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#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) {
    std::vector<std::vector<int>> tav(n, std::vector<int>(n, -1));

    for (const auto &k : kapcsolatok) {
        tav[k.first - 1][k.second - 1] = 1;
        tav[k.second - 1][k.first - 1] = 1;
    }

    for (int i = 0; i < n; i++) {
        tav[i][i] = 0;
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (tav[i][k] != -1 && tav[k][j] != -1 && (tav[i][j] == -1 || tav[i][k] + tav[k][j] < tav[i][j])) {
                    tav[i][j] = tav[i][k] + tav[k][j];
                }
            }
        }
    }

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

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

    std::vector<int> zero_paciensek;
    for (int p = 0; p < n; p++) {
        if (zero_jelolt[p]) {
            if (k == 1) {
                zero_paciensek.push_back(p);
                continue;
            }

            const auto &p_tav = tav[p];

            int f;
            for (f = 1; f < k && p_tav[f_sorozat[f]] == p_tav[f_sorozat[0]]; f++) { }

            std::vector<int> teljes_sorrend(n);
            iota(teljes_sorrend.begin(), teljes_sorrend.end(), 0);
            sort(teljes_sorrend.begin(), teljes_sorrend.end(), [&](int a, int b) { return p_tav[a] < p_tav[b]; });

            int t;
            for (t = 0; t < n && p_tav[teljes_sorrend[t]] <= p_tav[f_sorozat[0]]; t++) { }
            t -= f;

            int i;
            for (i = 0; i < k && t + i < n && p_tav[teljes_sorrend[t + i]] == p_tav[f_sorozat[i]]; i++) { }

            if (i == k) {
                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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms564 KiB
2Accepted0/03ms392 KiB
3Accepted0/029ms648 KiB
4Accepted2/23ms384 KiB
5Accepted2/24ms356 KiB
6Accepted2/228ms756 KiB
7Accepted2/228ms688 KiB
8Accepted2/229ms612 KiB
9Accepted2/230ms668 KiB
10Accepted2/2208ms1452 KiB
11Accepted1/13ms504 KiB
12Accepted2/2152ms1380 KiB
13Accepted2/2153ms1380 KiB
14Accepted2/2175ms1344 KiB
15Accepted2/2160ms1436 KiB
16Accepted2/2150ms1484 KiB
17Accepted2/2150ms1508 KiB
18Accepted1/1158ms1508 KiB
19Accepted1/1149ms1512 KiB
20Accepted1/1150ms1380 KiB
21Accepted1/1209ms1380 KiB
22Accepted1/1197ms1528 KiB
23Accepted1/1174ms1380 KiB
24Accepted1/1170ms1312 KiB
25Accepted1/1194ms1380 KiB
26Accepted1/1216ms1504 KiB
27Accepted1/1215ms1380 KiB
28Accepted1/1175ms1552 KiB
29Accepted1/1180ms1380 KiB
30Accepted1/1170ms1428 KiB
31Accepted1/1174ms1416 KiB
32Accepted1/1206ms1252 KiB
33Accepted1/1208ms1444 KiB
34Accepted1/1211ms1404 KiB
35Accepted1/1210ms1532 KiB
36Accepted1/1211ms1380 KiB
37Accepted1/1212ms1380 KiB
38Accepted1/1210ms1380 KiB
39Accepted1/1177ms1380 KiB
40Accepted1/1204ms1512 KiB