238432026-01-30 17:24:17balintmarotiFertőzési sorozat (50 pont)cpp17Accepted 50/5017ms508 KiB
#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    int m;
    int k;
    cin >> n;
    cin >> m;
    cin >> k;

    vector<bool> not_target(n, true);
    vector<int> target;

    for (int i = 0; i < k; i++) {
        int a;
        cin >> a;

        target.push_back(a - 1);
        not_target[a - 1] = false;
    }

    vector<vector<int>> connections(n, vector<int>());

    for (int i = 0; i < m; i++) {
        int a;
        int b;
        cin >> a;
        cin >> b;

        connections[a - 1].push_back(b - 1);
        connections[b - 1].push_back(a - 1);
    }

    vector<int> solutions;

    for (int i = 0; i < n; i++) {
        vector<int> depth(n, -1);
        depth[i]=0;
        vector<int> q = {i};
        int index = 0;

        while (index < q.size()) {
            for (int x = 0; x < connections[q[index]].size(); x++) {
                if (depth[connections[q[index]][x]] == -1) {
                    q.push_back(connections[q[index]][x]);
                    depth[connections[q[index]][x]] = depth[q[index]] + 1;
                }
            }
            index += 1;
        }

        //for (int x : depth) cout << x << " ";
        //cout << endl;

        bool good = true;
        int previous = -1;
        for (int x : target) {
            if (depth[x] >= previous) {
                previous = depth[x];
            } else {
                good = false;
                break;
            }
        }

        if (good) {
            int lowbound = depth[target[0]];
            int highbound = depth[target[target.size() - 1]];

            for (int x = 0; x < n; x++) {
                if (not_target[x] && lowbound < depth[x] && depth[x] < highbound) {
                    good = false;
                    break;
                }
            }
        }

        if(good) solutions.push_back(i);
    }

    cout << solutions.size() << endl;

    for (int i : solutions) cout << i + 1 << " ";

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/01ms316 KiB
3Accepted0/04ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/22ms316 KiB
6Accepted2/24ms316 KiB
7Accepted2/24ms316 KiB
8Accepted2/24ms316 KiB
9Accepted2/26ms316 KiB
10Accepted2/217ms316 KiB
11Accepted1/11ms316 KiB
12Accepted2/27ms352 KiB
13Accepted2/28ms456 KiB
14Accepted2/24ms316 KiB
15Accepted2/28ms500 KiB
16Accepted2/28ms316 KiB
17Accepted2/24ms456 KiB
18Accepted1/17ms316 KiB
19Accepted1/18ms460 KiB
20Accepted1/16ms460 KiB
21Accepted1/116ms464 KiB
22Accepted1/117ms500 KiB
23Accepted1/114ms316 KiB
24Accepted1/113ms460 KiB
25Accepted1/113ms316 KiB
26Accepted1/114ms468 KiB
27Accepted1/116ms508 KiB
28Accepted1/114ms460 KiB
29Accepted1/114ms460 KiB
30Accepted1/113ms316 KiB
31Accepted1/113ms460 KiB
32Accepted1/114ms460 KiB
33Accepted1/116ms316 KiB
34Accepted1/116ms460 KiB
35Accepted1/117ms508 KiB
36Accepted1/116ms460 KiB
37Accepted1/116ms460 KiB
38Accepted1/116ms460 KiB
39Accepted1/114ms460 KiB
40Accepted1/116ms508 KiB