238432026-01-30 17:24:17balintmarotiFertőzési sorozat (50 pont)cpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/24ms316 KiB
7Elfogadva2/24ms316 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/26ms316 KiB
10Elfogadva2/217ms316 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/27ms352 KiB
13Elfogadva2/28ms456 KiB
14Elfogadva2/24ms316 KiB
15Elfogadva2/28ms500 KiB
16Elfogadva2/28ms316 KiB
17Elfogadva2/24ms456 KiB
18Elfogadva1/17ms316 KiB
19Elfogadva1/18ms460 KiB
20Elfogadva1/16ms460 KiB
21Elfogadva1/116ms464 KiB
22Elfogadva1/117ms500 KiB
23Elfogadva1/114ms316 KiB
24Elfogadva1/113ms460 KiB
25Elfogadva1/113ms316 KiB
26Elfogadva1/114ms468 KiB
27Elfogadva1/116ms508 KiB
28Elfogadva1/114ms460 KiB
29Elfogadva1/114ms460 KiB
30Elfogadva1/113ms316 KiB
31Elfogadva1/113ms460 KiB
32Elfogadva1/114ms460 KiB
33Elfogadva1/116ms316 KiB
34Elfogadva1/116ms460 KiB
35Elfogadva1/117ms508 KiB
36Elfogadva1/116ms460 KiB
37Elfogadva1/116ms460 KiB
38Elfogadva1/116ms460 KiB
39Elfogadva1/114ms460 KiB
40Elfogadva1/116ms508 KiB