251132026-02-18 00:30:16999Fertőzési sorozat (50 pont)cpp17Accepted 50/5016ms508 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

signed main() {
    int n,m,k;cin>>n>>m>>k;
    vector<vector<int>> v(n);
    vector<int> kap(k);
    for(int i = 0;i<k;i++){
        cin>>kap[i];
        kap[i]--;
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        v[--a].push_back(--b);
        v[b].push_back(a);
    }
	vector<int> dis(n),tav(k),ans,vane(n),hany(n);
	queue<int> q;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++)dis[j]=1e12;
        for(int j = 0;j<n;j++){
            vane[j]=0;
            hany[j]=0;
        }
		dis[i]=0;
		q.push(i);
		while(!q.empty()){
			int a=q.front();
			q.pop();
			for(int u : v[a]){
				if(dis[u]==1e12){
					dis[u]=dis[a]+1;
					q.push(u);
				}
			}
		}
		for(int j = 0;j<k;j++){
			tav[j]=dis[kap[j]];
            hany[tav[j]]++;
		}
        for(int j = 0;j<n;j++)vane[dis[j]]++;
		bool lehet=true;
		for(int i = 1;i<k;i++){
			if(!lehet)break;
			if(!(tav[i]==tav[i-1]||tav[i]==tav[i-1]+1)||tav[i]==1e12)lehet=false;
		}
        for(int i = 0;i<n;i++){
            if(!lehet)break;
            if(vane[i]!=hany[i]&&i!=tav[0]&&i!=tav[k-1]&&hany[i]>0)lehet=false;
        }
		if(lehet&&tav[0]!=1e12)ans.push_back(i);
        //cout<<i<<':'<<endl;
        //for(int j : dis)cout<<j<<' ';
        //cout<<endl;
	}
	cout<<ans.size()<<endl;
	for(int i : ans)cout<<i+1<<' ';
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms492 KiB
2Accepted0/01ms316 KiB
3Accepted0/04ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/22ms316 KiB
6Accepted2/24ms420 KiB
7Accepted2/24ms420 KiB
8Accepted2/24ms316 KiB
9Accepted2/24ms444 KiB
10Accepted2/216ms316 KiB
11Accepted1/11ms316 KiB
12Accepted2/28ms316 KiB
13Accepted2/28ms316 KiB
14Accepted2/26ms316 KiB
15Accepted2/27ms452 KiB
16Accepted2/28ms508 KiB
17Accepted2/26ms448 KiB
18Accepted1/17ms384 KiB
19Accepted1/18ms444 KiB
20Accepted1/16ms500 KiB
21Accepted1/116ms500 KiB
22Accepted1/114ms316 KiB
23Accepted1/113ms456 KiB
24Accepted1/113ms456 KiB
25Accepted1/110ms456 KiB
26Accepted1/114ms332 KiB
27Accepted1/116ms456 KiB
28Accepted1/113ms448 KiB
29Accepted1/114ms316 KiB
30Accepted1/112ms500 KiB
31Accepted1/113ms316 KiB
32Accepted1/114ms332 KiB
33Accepted1/116ms316 KiB
34Accepted1/116ms460 KiB
35Accepted1/116ms316 KiB
36Accepted1/114ms456 KiB
37Accepted1/116ms456 KiB
38Accepted1/116ms456 KiB
39Accepted1/114ms316 KiB
40Accepted1/116ms508 KiB