Submission #919000

#	Time	Username	Problem	Language	Result	Execution time	Memory
919000		NK_	Newspapers (CEOI21_newspapers)	C++17	100 / 100	50 ms	8344 KiB

newspapers

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	V<vi> adj(N);
	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	if (M != N - 1) {
		cout << "NO" << nl;
		exit(0-0);
	}

	if (N == 1) {
		cout << "YES" << nl;
		cout << 1 << nl;
		cout << 1 << nl;
		exit(0-0);
	}

	if (N == 2) {
		cout << "YES" << nl;
		cout << 2 << nl;
		cout << 1 << " " << 1 << nl;
		exit(0-0);
	}

	vi D(N, -1), par(N);
	auto bfs = [&]() {
		vi q; for(int i = 0; i < N; i++) if (D[i] == 0) q.pb(i);

		for(int i = 0; i < sz(q); i++) {
			int u = q[i];

			for(auto& v : adj[u]) if (D[v] == -1) {
				D[v] = D[u] + 1; par[v] = u;
				q.pb(v);
			}
		}
	};

	D = vi(N, -1); D[0] = 0; bfs();
	int s = max_element(begin(D), end(D)) - begin(D);
	D = vi(N, -1); D[s] = 0; bfs();
	int t = max_element(begin(D), end(D)) - begin(D);
	D = vi(N, -1); D[t] = 0; bfs();

	vi path;
	for(int u = par[s]; u != t; u = par[u]) path.pb(u);

	D = vi(N, -1); for(auto& u : path) D[u] = 0;
	bfs();

	if (*max_element(begin(D), end(D)) > 2) {
		cout << "NO" << nl;
		exit(0-0);
	}

	vi ans;
	for(int i = 0; i < sz(path); i++) {
		int u = path[i];
		ans.pb(u);
		for(auto& v : adj[u]) if (D[v] && sz(adj[v]) > 1) {
			ans.pb(v); ans.pb(u);
		}
	}

	cout << "YES" << nl;
	cout << 2 * sz(ans) << nl;
	for(auto& x : ans) cout << x + 1 << " ";
	reverse(begin(ans), end(ans));
	for(auto& x : ans) cout << x + 1 << " ";
	cout << nl;

	exit(0-0);
}

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