149452025-02-09 11:02:18miszorimarciFertőzési sorozat (50 pont)cpp17Accepted 50/5017ms508 KiB
#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> a(K);
    for (int& x : a) cin >> x;
    set<int> aSet(a.begin(), a.end());
    vector<vector<int>> g(N + 1);
    while (M--) {
        int U, V;
        cin >> U >> V;
        g[U].push_back(V);
        g[V].push_back(U);
    }
    vector<int> ans;
    for (int start = 1; start <= N; start++) {
        vector<int> vis(N + 1);
        vis[start] = 1;
        queue<int> q({start});

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : g[u]) {
                if (!vis[v]) {
                    vis[v] = vis[u] + 1;
                    q.push(v);
                }
            }
        }
        vector<int> order(K);
        set<int> orderSet;
        for (int i = 0; i < K; i++) {
            orderSet.insert(order[i] = vis[a[i]]);
        }
        bool ok = 1;
        for (int i = 1; i < K; i++) {
            int d = order[i] - order[i - 1];
            ok = ok && (d == 0 || d == 1);
        }
        orderSet.erase(orderSet.begin());
        if (!orderSet.empty()) {
            orderSet.erase(*orderSet.rbegin());
        }
        for (int u = 1; u <= N; u++) {
            ok = ok && !(!aSet.count(u) &&
                         orderSet.count(vis[u]));
        }
        if (ok) { ans.push_back(start); }
    }
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/01ms316 KiB
3Accepted0/04ms508 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/24ms496 KiB
7Accepted2/23ms508 KiB
8Accepted2/24ms444 KiB
9Accepted2/24ms452 KiB
10Accepted2/213ms500 KiB
11Accepted1/11ms316 KiB
12Accepted2/26ms316 KiB
13Accepted2/27ms508 KiB
14Accepted2/24ms316 KiB
15Accepted2/26ms472 KiB
16Accepted2/26ms460 KiB
17Accepted2/24ms460 KiB
18Accepted1/14ms316 KiB
19Accepted1/16ms460 KiB
20Accepted1/14ms508 KiB
21Accepted1/112ms508 KiB
22Accepted1/112ms472 KiB
23Accepted1/110ms464 KiB
24Accepted1/19ms464 KiB
25Accepted1/19ms508 KiB
26Accepted1/110ms472 KiB
27Accepted1/112ms316 KiB
28Accepted1/19ms316 KiB
29Accepted1/110ms316 KiB
30Accepted1/19ms468 KiB
31Accepted1/19ms508 KiB
32Accepted1/19ms316 KiB
33Accepted1/117ms316 KiB
34Accepted1/112ms464 KiB
35Accepted1/112ms316 KiB
36Accepted1/112ms316 KiB
37Accepted1/112ms464 KiB
38Accepted1/112ms464 KiB
39Accepted1/110ms468 KiB
40Accepted1/114ms340 KiB