99192024-03-18 16:55:53111Pletykacpp17Time limit exceeded 94/100128ms48820 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("be2.txt","r",stdin);
//	freopen("out.txt","w",stdout);
#endif
    int N,M,K;
    cin>>N>>M>>K;
    int it=N*2+2;
    vector<int>v(N+1,-1);
    deque<int>q;
    for(int i=0;i<K;i++){
		int a;
		cin>>a;
		v[a]=0;
		q.push_back(a);
    }
    vector<vector<int>>g(N+1);
    for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
    }
    while(!q.empty()){
		int i=q.front();
		q.pop_front();
		for(int j:g[i]){
			if(v[j]==-1){
				v[j]=v[i]+1;
				q.push_back(j);
			}
		}
    }
    vector<vector<int>>d(it);
    vector<int>w(N+1,-1);
    for(int i=1;i<=N;i++){
		if(v[i]==-1){
			continue;
		}
		int x=INT_MAX;
		for(int j:g[i]){
			if(v[j]>=v[i]&&v[j]%2==v[i]%2){
				x=min(x,v[j]);
			}
		}
		if(x!=INT_MAX){
			w[i]=x;
			d[x].push_back(i);
		}
    }
    for(int i=0;i<it;i++){
		for(int j:d[i]){
			if(w[j]<i){
				continue;
			}
			for(int k:g[j]){
				if(w[k]==-1||w[k]>i+1){
					w[k]=i+1;
					d[i+1].push_back(k);
				}
			}
		}
    }
    vector<array<int,2>>b(it);
    vector<int>pf(it);
    int e=0;
    for(int i=1;i<=N;i++){
		if(v[i]==-1){
			continue;
		}
		if (g[i].empty()){
			e++;
			continue;
		}
		b[v[i]][v[i]%2]++;
		if(w[i]==-1){
			continue;
		}
		b[w[i]][v[i]%2]--;
		pf[w[i]]++;
    }
    vector<int>ans(it);
    array<int,2>c{};
    for(int i=0;i<it;i++){
		c[0]+=b[i][0]+pf[i];
		c[1]+=b[i][1]+pf[i];
		ans[i]=c[i%2];
    }
    ans[0]+=e;
    int P=max_element(ans.begin(),ans.end())-ans.begin();
    cout<<ans[P]<<'\n';
    cout<<P+1<<'\n';
    for(int i=0;i<=P;i++){
		cout<<ans[i]<<' ';
    }
    cout<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base94/100
1Accepted0/03ms1828 KiB
2Accepted0/025ms13720 KiB
3Accepted2/23ms2556 KiB
4Accepted2/23ms3204 KiB
5Accepted2/24ms3876 KiB
6Accepted2/26ms5260 KiB
7Accepted4/46ms5268 KiB
8Accepted4/48ms7152 KiB
9Accepted4/48ms7064 KiB
10Accepted4/48ms7452 KiB
11Accepted4/423ms15484 KiB
12Accepted4/420ms15120 KiB
13Accepted4/434ms22076 KiB
14Accepted4/437ms23168 KiB
15Accepted6/650ms30904 KiB
16Accepted6/650ms30748 KiB
17Accepted6/664ms38056 KiB
18Accepted6/665ms39056 KiB
19Accepted6/664ms40760 KiB
20Accepted6/668ms41816 KiB
21Accepted6/668ms41792 KiB
22Accepted6/675ms43284 KiB
23Time limit exceeded0/6128ms48820 KiB
24Accepted6/6119ms48812 KiB