Submission #1190845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190845		PieArmy	Newspapers (CEOI21_newspapers)	C++20	100 / 100	40 ms	4680 KiB

newspapers

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n,m;
vector<int>komsu[1023];
vector<int>ans;
int par[1023],dep[1023],pari[1023];
vector<int>a[2][2];

void cal(int pos){
	dep[pos]=0;
	for(int x:komsu[pos]){
		if(par[pos]==x)continue;
		pari[x]=pari[pos]^1;
		par[x]=pos;
		cal(x);
		dep[pos]=max(dep[pos],dep[x]+1);
	}
}

bool dfs(int pos){
	vector<int>child;
	for(int x:komsu[pos]){
		if(par[pos]==x)continue;
		child.pb(x);
	}
	sort(child.begin(),child.end(),[&](const int &x,const int &y){
		return dep[x]>dep[y];
	});
	if(child.size()==0)return true;
	if(child.size()>1){
		if(dep[child[1]]>1)return false;
	}
	if(dep[child[0]]==0){
		ans.pb(pos);
		return true;
	}
	for(int x:child){
		if(dep[x]==0)break;
		if(!dfs(x))return false;
		if(par[pos]==0&&child.size()==1)break;
		ans.pb(pos);
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	if(m!=n-1){
		cout<<"NO"<<endl;
		return 0;
	}
	if(n<=2){
		cout<<"YES"<<endl<<n<<endl;
		for(int i=0;i<n;i++){
			cout<<"1 ";
		}
		cout<<endl;
		return 0;
	}
	for(int root=1;root<=n;root++){
		par[root]=0;
		cal(root);
		if(dfs(root)){
			int t=(komsu[root].size()==1)^((pari[root]&1)^(pari[1]&1));
			if(a[1][t].size()==0||a[1][t].size()>ans.size()){
				a[1][t]=ans;
			}
			if(a[1][t^1].size()==0||a[1][t^1].size()>ans.size()+1){
				a[1][t^1]=ans;
				a[1][t^1].pb(1);
			}
			t^=(int(ans.size())&1)^1;
			if(a[0][t].size()==0||a[0][t].size()>ans.size()){
				a[0][t]=ans;
			}
			if(a[0][t^1].size()==0||a[0][t^1].size()>ans.size()+1){
				a[0][t^1]=ans;
				a[0][t^1].pb(1);
			}
		}
		ans.clear();
	}
	if(a[0][0].size()){
		cout<<"YES"<<endl;
		int x=a[0][0].size()+a[1][0].size(),y=a[0][1].size()+a[1][1].size();
		if(x<y){
			cout<<x<<endl;
			for(int c:a[1][0]){
				cout<<c<<" ";
			}
			for(int c:a[0][0]){
				cout<<c<<" ";
			}
			cout<<endl;
		}
		else{
			cout<<y<<endl;
			for(int c:a[1][1]){
				cout<<c<<" ";
			}
			for(int c:a[0][1]){
				cout<<c<<" ";
			}
			cout<<endl;
		}
	}
	else cout<<"NO"<<endl;
}

• Subtask 1: 12 / 12
• Subtask 2: 8 / 8
• Subtask 3: 80 / 80