Submission #576910

#	Time	Username	Problem	Language	Result	Execution time	Memory
576910		amunduzbaev	Newspapers (CEOI21_newspapers)	C++17	100 / 100	2 ms	480 KiB

newspapers

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int N = 1005;
vector<int> edges[N];
int d[N], par[N], used[N], is[N];

void dfs(int u, int p = -1){
	for(auto x : edges[u]){
		if(x == p) continue;
		par[x] = u;
		d[x] = d[u] + 1;
		dfs(x, u);
	}
}

int dfs2(int u, int p = -1, int d = 0){
	int mx = d;
	for(auto x : edges[u]){
		if(x == p || used[x]) continue;
		mx = max(mx, dfs2(x, u, d + 1));
	} 
	if(mx > d && d) is[u] = 1;
	return mx;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	if(n == 1){
		cout<<"YES\n";
		cout<<1<<"\n"<<1<<"\n";
		return 0;
	}
	if(n == 2){
		cout<<"YES\n";
		cout<<2<<"\n"<<1<<" "<<1<<"\n";
		return 0;
	}
	if(m >= n){
		cout<<"NO\n";
		return 0;
	}
	
	for(int i=0;i<m;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	int a = 1, b = 1;
	d[a] = 0, dfs(a);
	b = max_element(d+1, d+n+1) - d;
	d[b] = 0, dfs(b);
	a = max_element(d+1, d+n+1) - d;
	
	vector<int> p;
	while(a != b){
		p.push_back(a);
		a = par[a];
	} p.push_back(a);
	
	for(auto x : p) used[x] = 1;
	int mx = 0;
	for(auto x : p){
		mx = max(mx, dfs2(x));
	}
	
	if(mx >= 3){
		cout<<"NO\n";
		return 0;
	}
	
	vector<int> rev;
	for(int i=1;i+1<(int)p.size();i++){
		int u = p[i];
		rev.push_back(u);
		for(auto x : edges[u]){
			if(is[x]){
				rev.push_back(x);
				rev.push_back(u);
			}
		}
	}
	
	
	vector<int> tt = rev;
	reverse(tt.begin(), tt.end());
	rev.insert(rev.end(), tt.begin(), tt.end());
	cout<<"YES\n";
	cout<<(int)rev.size()<<"\n";
	for(auto x : rev) cout<<x<<" ";
	cout<<"\n";
}
 

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