237182026-01-28 09:18:02TtestFertőzési sorozat (50 pont)cpp17Wrong answer 42/5012ms644 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    vector<int> f(K);
    for (int i = 0; i < K; i++) {
        cin >> f[i];
        f[i]--; // 0-indexelés
    }

    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> result;

    // Minden lehetséges zéró páciens kipróbálása
    for (int start = 0; start < N; start++) {

        // BFS távolságok
        vector<int> dist(N, -1);
        queue<int> q;
        dist[start] = 0;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int to : adj[v]) {
                if (dist[to] == -1) {
                    dist[to] = dist[v] + 1;
                    q.push(to);
                }
            }
        }

        bool ok = true;

        // A megadott fertőzési részsorozat ellenőrzése
        for (int i = 0; i + 1 < K && ok; i++) {
            int d1 = dist[f[i]];
            int d2 = dist[f[i + 1]];

            // Nem ugorhat vissza vagy kettőt előre
            if (d2 < d1 || d2 > d1 + 1) {
                ok = false;
                break;
            }

            // Ha ugyanazon a napon fertőződtek,
            // nem lehet köztük "kényszerítő" kapcsolat
            if (d2 == d1) {
                for (int to : adj[f[i]]) {
                    if (to == f[i + 1] && dist[to] == d1 + 1) {
                        ok = false;
                        break;
                    }
                }
            }

            // Ha következő nap fertőződött,
            // kell legyen szomszédja az előző vagy korábbi rétegben
            if (d2 == d1 + 1) {
                bool has_prev = false;
                for (int to : adj[f[i + 1]]) {
                    if (dist[to] == d1) {
                        has_prev = true;
                        break;
                    }
                }
                if (!has_prev) {
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            result.push_back(start + 1); // vissza 1-indexre
        }
    }

    cout << result.size() << "\n";
    for (int x : result) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base42/50
1Accepted0/01ms316 KiB
2Accepted0/01ms508 KiB
3Accepted0/03ms508 KiB
4Accepted2/21ms316 KiB
5Accepted2/22ms316 KiB
6Accepted2/23ms316 KiB
7Accepted2/23ms436 KiB
8Accepted2/23ms332 KiB
9Accepted2/24ms316 KiB
10Accepted2/212ms464 KiB
11Accepted1/11ms316 KiB
12Accepted2/24ms316 KiB
13Accepted2/24ms316 KiB
14Accepted2/23ms316 KiB
15Accepted2/24ms316 KiB
16Accepted2/26ms456 KiB
17Accepted2/23ms388 KiB
18Accepted1/14ms500 KiB
19Accepted1/14ms508 KiB
20Accepted1/13ms564 KiB
21Accepted1/112ms508 KiB
22Accepted1/110ms468 KiB
23Accepted1/19ms316 KiB
24Wrong answer0/18ms460 KiB
25Accepted1/18ms456 KiB
26Accepted1/110ms316 KiB
27Wrong answer0/112ms464 KiB
28Wrong answer0/19ms316 KiB
29Accepted1/110ms316 KiB
30Wrong answer0/18ms508 KiB
31Wrong answer0/18ms456 KiB
32Accepted1/19ms460 KiB
33Accepted1/112ms316 KiB
34Wrong answer0/112ms468 KiB
35Wrong answer0/112ms456 KiB
36Wrong answer0/112ms316 KiB
37Accepted1/112ms644 KiB
38Accepted1/112ms460 KiB
39Accepted1/19ms316 KiB
40Accepted1/112ms544 KiB