152952025-02-18 09:06:04AblablablaFertőzési sorozat (50 pont)cpp17Accepted 50/5019ms596 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> alap(k);
    for(int &x : alap){
        cin >> x;
        x--;
    }

    vector<vector<int>> csucsok(n, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
    }

    vector<int> ans;

    for(int kezd = 0; kezd < n; kezd++){
        vector<bool> bejart(n);
        vector<int> tav(n, 2e9 + 7);
        int maxi = 0;
        queue<int> bejar;
        bejar.push(kezd);
        tav[kezd] = 0;

        while(!bejar.empty()){
            int akt = bejar.front();
            maxi = max(maxi, tav[akt]);
            bejar.pop();

            if(bejart[akt]) continue;

            bejart[akt] = 1;

            for(int x : csucsok[akt]){
                if(bejart[x]) continue;

                tav[x] = min(tav[x], tav[akt] + 1);
                bejar.push(x);
            }
        }

        vector<int> db(maxi + 1);
        for(int x : tav){
            db[x]++;
        }

        bool jo = 1;
        int elozo = tav[alap[0]];
        bool elso = 1;
        db[elozo]--;
        for(int i = 1; i < k; i++){
            int akt = tav[alap[i]];

            if(elozo != akt){
                if(akt < elozo || akt - elozo >= 2 || (!elso && db[elozo] != 0)){
                    jo = 0;
                    break;
                }
                elso = 0;
                elozo = akt;
            }

            db[akt]--;
        }

        if(jo){
            ans.push_back(kezd + 1);
        }
    }

    cout << ans.size() << "\n";
    for(int x : ans){
        cout << x << " ";
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/01ms500 KiB
3Accepted0/06ms316 KiB
4Accepted2/21ms500 KiB
5Accepted2/22ms316 KiB
6Accepted2/24ms316 KiB
7Accepted2/24ms316 KiB
8Accepted2/24ms320 KiB
9Accepted2/27ms424 KiB
10Accepted2/219ms436 KiB
11Accepted1/12ms316 KiB
12Accepted2/27ms440 KiB
13Accepted2/27ms316 KiB
14Accepted2/26ms436 KiB
15Accepted2/27ms436 KiB
16Accepted2/28ms432 KiB
17Accepted2/26ms432 KiB
18Accepted1/17ms420 KiB
19Accepted1/17ms432 KiB
20Accepted1/16ms440 KiB
21Accepted1/119ms500 KiB
22Accepted1/119ms376 KiB
23Accepted1/117ms432 KiB
24Accepted1/117ms436 KiB
25Accepted1/116ms440 KiB
26Accepted1/117ms432 KiB
27Accepted1/119ms436 KiB
28Accepted1/117ms432 KiB
29Accepted1/118ms432 KiB
30Accepted1/117ms436 KiB
31Accepted1/117ms436 KiB
32Accepted1/117ms436 KiB
33Accepted1/119ms316 KiB
34Accepted1/119ms436 KiB
35Accepted1/119ms432 KiB
36Accepted1/119ms316 KiB
37Accepted1/119ms596 KiB
38Accepted1/119ms436 KiB
39Accepted1/117ms436 KiB
40Accepted1/119ms436 KiB