238412026-01-30 17:05:41Rokus23Fertőzési sorozat (50 pont)cpp17Accepted 50/5013ms552 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

bool init(vector<int>& v, int N) {
	for(int i=0;i<v.size();i++) {
		if(v[i]==N) return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
	int N,M,K;cin>>N>>M>>K;
	vector<vector<int>> g(N);
	vector<int> s(K);
	for(int i=0;i<K;i++) cin>>s[i];
	for(int i=0;i<K;i++) s[i]--;
	for(int i=0;i<M;i++) {
		int a,b;
		cin>>a>>b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	vector<int> ans;
	for(int i=0;i<N;i++) {
		queue<int> q;
		vector<int> d(N,-1);
		d[i]=0;
		q.push(i);
		while(!q.empty()) {
			int v=q.front();
			q.pop();
			for(int u:g[v]) {
				if(d[u]==-1) {
					d[u]=d[v]+1;
					q.push(u);
				}
			}
		}
		bool b=true;
		for(int j=0;j<K-1;j++) if(d[s[j]]>d[s[j+1]]) b=false;
		if(b) {
			int m2=d[s[0]],m1=d[s[K-1]];
			for(int j=0;j<N;j++) if(!init(s,j) && d[j]<m1 && d[j]>m2) b=false;
		}
		if(b) ans.push_back(i+1);
	}
	cout<<ans.size()<<"\n";
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms316 KiB
2Accepted0/02ms316 KiB
3Accepted0/04ms316 KiB
4Accepted2/22ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/24ms316 KiB
7Accepted2/23ms316 KiB
8Accepted2/24ms448 KiB
9Accepted2/24ms316 KiB
10Accepted2/213ms468 KiB
11Accepted1/11ms316 KiB
12Accepted2/27ms468 KiB
13Accepted2/28ms316 KiB
14Accepted2/26ms316 KiB
15Accepted2/27ms460 KiB
16Accepted2/27ms316 KiB
17Accepted2/24ms316 KiB
18Accepted1/14ms316 KiB
19Accepted1/16ms456 KiB
20Accepted1/17ms552 KiB
21Accepted1/110ms456 KiB
22Accepted1/110ms456 KiB
23Accepted1/18ms316 KiB
24Accepted1/18ms456 KiB
25Accepted1/110ms508 KiB
26Accepted1/19ms316 KiB
27Accepted1/112ms456 KiB
28Accepted1/19ms316 KiB
29Accepted1/110ms464 KiB
30Accepted1/112ms456 KiB
31Accepted1/19ms440 KiB
32Accepted1/19ms456 KiB
33Accepted1/112ms316 KiB
34Accepted1/112ms316 KiB
35Accepted1/113ms316 KiB
36Accepted1/112ms316 KiB
37Accepted1/110ms460 KiB
38Accepted1/110ms460 KiB
39Accepted1/19ms532 KiB
40Accepted1/112ms460 KiB