237182026-01-28 09:18:02TtestFertőzési sorozat (50 pont)cpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base42/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms508 KiB
3Elfogadva0/03ms508 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/23ms316 KiB
7Elfogadva2/23ms436 KiB
8Elfogadva2/23ms332 KiB
9Elfogadva2/24ms316 KiB
10Elfogadva2/212ms464 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/24ms316 KiB
13Elfogadva2/24ms316 KiB
14Elfogadva2/23ms316 KiB
15Elfogadva2/24ms316 KiB
16Elfogadva2/26ms456 KiB
17Elfogadva2/23ms388 KiB
18Elfogadva1/14ms500 KiB
19Elfogadva1/14ms508 KiB
20Elfogadva1/13ms564 KiB
21Elfogadva1/112ms508 KiB
22Elfogadva1/110ms468 KiB
23Elfogadva1/19ms316 KiB
24Hibás válasz0/18ms460 KiB
25Elfogadva1/18ms456 KiB
26Elfogadva1/110ms316 KiB
27Hibás válasz0/112ms464 KiB
28Hibás válasz0/19ms316 KiB
29Elfogadva1/110ms316 KiB
30Hibás válasz0/18ms508 KiB
31Hibás válasz0/18ms456 KiB
32Elfogadva1/19ms460 KiB
33Elfogadva1/112ms316 KiB
34Hibás válasz0/112ms468 KiB
35Hibás válasz0/112ms456 KiB
36Hibás válasz0/112ms316 KiB
37Elfogadva1/112ms644 KiB
38Elfogadva1/112ms460 KiB
39Elfogadva1/19ms316 KiB
40Elfogadva1/112ms544 KiB