제출 #1190799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190799		PieArmy	Newspapers (CEOI21_newspapers)	C++20	75 / 100	41 ms	4676 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;
vector<int>anss;
int par[1023],dep[1023];

void cal(int pos){
	dep[pos]=0;
	for(int x:komsu[pos]){
		if(par[pos]==x)continue;
		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 t;

void dfs2(int pos){
	if(dep[pos]==0)return;
	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(dep[child[0]]==0){
		ans.pb(pos);
		return;
	}
	for(int x:child){
		if(dep[x]==0)break;
		dfs2(x);
		ans.pb(pos);
	}
	if(par[pos]==0&&dep[child.back()]!=0){
		ans.pop_back();
	}
}

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)){
			t=(dep[root])&1;
			if(komsu[root].size()==1)t^=1;
			if((dep[ans[0]]&1)!=((dep[root]&1)!=(komsu[root].size()==1))){
				ans.pb(ans[0]);
				t^=1;
			}
			dfs2(root);
			if(anss.size()==0||anss.size()>ans.size()){
				swap(ans,anss);
			}
		}
		ans.clear();
	}
	if(anss.size()){
		cout<<"YES"<<endl<<anss.size()<<endl;
		for(int x:anss)
			cout<<x<<" ";
		cout<<endl;
	}
	else cout<<"NO"<<endl;
}

• Subtask 1: 9 / 12
• Subtask 2: 6 / 8
• Subtask 3: 60 / 80