251132026-02-18 00:30:16999Fertőzési sorozat (50 pont)cpp17Elfogadva 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<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms492 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/24ms420 KiB
7Elfogadva2/24ms420 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/24ms444 KiB
10Elfogadva2/216ms316 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/28ms316 KiB
13Elfogadva2/28ms316 KiB
14Elfogadva2/26ms316 KiB
15Elfogadva2/27ms452 KiB
16Elfogadva2/28ms508 KiB
17Elfogadva2/26ms448 KiB
18Elfogadva1/17ms384 KiB
19Elfogadva1/18ms444 KiB
20Elfogadva1/16ms500 KiB
21Elfogadva1/116ms500 KiB
22Elfogadva1/114ms316 KiB
23Elfogadva1/113ms456 KiB
24Elfogadva1/113ms456 KiB
25Elfogadva1/110ms456 KiB
26Elfogadva1/114ms332 KiB
27Elfogadva1/116ms456 KiB
28Elfogadva1/113ms448 KiB
29Elfogadva1/114ms316 KiB
30Elfogadva1/112ms500 KiB
31Elfogadva1/113ms316 KiB
32Elfogadva1/114ms332 KiB
33Elfogadva1/116ms316 KiB
34Elfogadva1/116ms460 KiB
35Elfogadva1/116ms316 KiB
36Elfogadva1/114ms456 KiB
37Elfogadva1/116ms456 KiB
38Elfogadva1/116ms456 KiB
39Elfogadva1/114ms316 KiB
40Elfogadva1/116ms508 KiB