238412026-01-30 17:05:41Rokus23Fertőzési sorozat (50 pont)cpp17Elfogadva 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]<<" ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/02ms316 KiB
2Elfogadva0/02ms316 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/22ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/24ms316 KiB
7Elfogadva2/23ms316 KiB
8Elfogadva2/24ms448 KiB
9Elfogadva2/24ms316 KiB
10Elfogadva2/213ms468 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/27ms468 KiB
13Elfogadva2/28ms316 KiB
14Elfogadva2/26ms316 KiB
15Elfogadva2/27ms460 KiB
16Elfogadva2/27ms316 KiB
17Elfogadva2/24ms316 KiB
18Elfogadva1/14ms316 KiB
19Elfogadva1/16ms456 KiB
20Elfogadva1/17ms552 KiB
21Elfogadva1/110ms456 KiB
22Elfogadva1/110ms456 KiB
23Elfogadva1/18ms316 KiB
24Elfogadva1/18ms456 KiB
25Elfogadva1/110ms508 KiB
26Elfogadva1/19ms316 KiB
27Elfogadva1/112ms456 KiB
28Elfogadva1/19ms316 KiB
29Elfogadva1/110ms464 KiB
30Elfogadva1/112ms456 KiB
31Elfogadva1/19ms440 KiB
32Elfogadva1/19ms456 KiB
33Elfogadva1/112ms316 KiB
34Elfogadva1/112ms316 KiB
35Elfogadva1/113ms316 KiB
36Elfogadva1/112ms316 KiB
37Elfogadva1/110ms460 KiB
38Elfogadva1/110ms460 KiB
39Elfogadva1/19ms532 KiB
40Elfogadva1/112ms460 KiB