제출 #1150481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150481		bilgun	Newspapers (CEOI21_newspapers)	C++20	0 / 100	1093 ms	328 KiB

newspapers

#include<bits/stdc++.h>
using namespace std;

long long n, m, sum = 0;
vector<vector<long long>> g;
int par[1005], h[1005], path[1005];
int yno = 0;
vector<int> ans;

pair<int, int> dfs( int node, int parent) {
	int maxd = 0;
	int distm = node;
	for( auto it : g[node]) {
		if(it != parent) {
			par[it] = node;
			auto s = dfs(it, node);
			s.first++;
			if( s.first > maxd) {
				maxd = s.first;
				distm = s.second;
			}
		}
	}
	return {maxd, distm};
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	g.resize(n + 1);
	if( m != n - 1) {
		cout << "NO";
		return 0;
	}
	else if( n == 1) {
		cout << "YES" << endl;
		cout << 2 << endl;
		cout << "1 1" << endl;
		return 0;
	}
	else if( n == 2 ) {
		cout << "YES" << endl;
		cout << 2 << endl;
		cout << "1 1" << endl;
		return 0;
	}

	for( int i = 1; i <= m; i++)
	{
		long long a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	int u = dfs(1, -1).second;
	int v = dfs(u, -1).second;

	int curr = v;
	while(curr != u) {
		path[curr] = h[curr] = 1;
		for( auto it : g[curr]) {
			h[it] = 1;
			for( auto ed : g[it]) {
				h[it] = 1;
			}
		}
	}
	bool isUnvisited = false;
	for (int i = 1; i <= n; i++) {
		if (h[i] == 0) {
			isUnvisited = true;
			break;
		}
	}

	if (isUnvisited) {
		cout << "NO" << endl;
		return 0;
	}
	int cur = par[v];
	while (cur != u) {
		ans.push_back(cur);
		for (auto it : g[cur]) {
			if (g[it].size() == 1 || path[it]) continue;
			ans.push_back(it);
			ans.push_back(cur);
		}
		cur = par[cur];
	}
	cout << "YES" << endl;
    cout << 2 * ans.size() << endl;
    for (int x : ans) cout << x << " ";
    reverse(ans.begin(), ans.end());
    for (int x : ans) cout << x << " ";
    cout << endl;




	return 0;
}

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