Submission #592366

#	Time	Username	Problem	Language	Result	Execution time	Memory
592366		SeDunion	Newspapers (CEOI21_newspapers)	C++17	100 / 100	77 ms	28172 KiB

newspapers

#include <iostream>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;

const int N = 1e6 + 66;

int cycle;
vector<int>g[N];
 
int n;

int used[N];
 
void dfsdfs(int v, int p = -1) {
	used[v] = 1;
	for (int to : g[v]) if (to != p) {
		if (used[to] == 1) cycle = 1;
		if (used[to] == 0) dfsdfs(to, v);
	}
	used[v] = 2;
}

int d[N];

queue<int>q;

int p[N];

int bfs(int v) {
	for (int i = 1 ; i <= n ; ++ i) d[i] = ((int)g[i].size() == 1 ? -2 : -1);
	d[v] = 0;
	p[v] = 0;
	q.push(v);
	while (q.size()) {
		v = q.front(); q.pop();
		for (int to : g[v]) if (d[to] == -1) {
			d[to] = d[v] + 1;
			p[to] = v;
			q.push(to);
		}
	}
	for (int i = 1 ; i <= n ; ++ i) if (d[i] > d[v]) v = i;
	return v;
}

vector<int>temp;

void go(int v) {
	used[v] = 1;
	if ((int)g[v].size() == 1) return;
	temp.emplace_back(v);
	for (int to : g[v]) if (!used[to] && (int)g[to].size() > 1) {
		go(to);
		temp.emplace_back(v);
	}
}

int go(int v, int p1, int d = 1) {
	if (d == 3) return 1;
	for (int to : g[v]) if (to != p1 && go(to, v, d+1)) return 1;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int m;
	cin >> n >> m;
	if (n == 1) {
		cout << "YES\n1\n1";
		return 0;
	}
	if (n == 2) {
		cout << "YES\n2\n1 1";
		return 0;
	}
	while (m--) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	for (int i = 1 ; i <= n ; ++ i) {
		int cnt = 0;
		for (int j : g[i]) cnt += go(j, i, 1);
		if (cnt >= 3) {
			cout << "NO";
			return 0;
		}
	}
	for (int i = 1 ; i <= n ; ++ i) if (!used[i]) {
		dfsdfs(i);
	}
	if (cycle) {
		cout << "NO";
		return 0;
	}
	for (int i = 1 ; i <= n ; ++ i) used[i] = 0;
	vector<int>ans;
	int v = -1;
	for (int u = 1 ; u <= n ; ++ u) if ((int)g[u].size() >= 2) v = u;
	assert(v != -1);
	temp.clear();
	int x = bfs(v);
	int y = bfs(x);
	int z = y;
	for (int i = 1 ; i <= n ; ++ i) used[i] = 0;
	while (z > 0) {
		used[z] = 1;
		z = p[z];
	}
	z = y;
	while (z > 0) {
		go(z);
		z = p[z];
	}
	for (int i : temp) ans.emplace_back(i);
	if ((int)temp.size() % 2 == 0) reverse(temp.begin(), temp.end());
	for (int i : temp) ans.emplace_back(i);
	cout << "YES\n";
	cout << ans.size() << "\n";
	for (int i : ans) cout << i << " ";	
}

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