Submission #946941

#	Time	Username	Problem	Language	Result	Execution time	Memory
946941		Halym2007	Newspapers (CEOI21_newspapers)	C++17	100 / 100	147 ms	8276 KiB

newspapers

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
const int N = 1e3 + 5;
vector <int> v[N];
int uzyn[N], par[N], vis[N], bolonok, val;
vector <int> jog;
void dfs (int x, int pr) {
	for (int i : v[x]) {
		if (i == pr) continue;
		uzyn[i] = uzyn[x] + 1;
		par[i] = x;
		dfs (i, x);
	}
}
 
void barla (int x, int pr) {
//	cout << x << " " << pr << "\n"; 
	for (int i : v[x]) {
		if (i == pr) continue;
		if (vis[i]) continue;
		val++;
		if (val >= 3) {
			bolonok = 1;
		}
		barla (i, x);
		val--;
	}
}
 
 
int main () {
//	freopen ("input1.txt", "r", stdin);
	int n, m, subtask1 = 0;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r;
		v[l].pb (r);
		v[r].pb (l);
		if (r - l != 1) subtask1 = 1;
	}
	if (m >= n) {
		cout << "NO\n";
	}
	else if (n <= 2) {
		cout << "YES\n";
		cout << n << "\n";
		for (int i = 1; i <= n; ++i) {
			cout << n << " ";
		}
	}
	else if (!subtask1) {
		cout << "YES\n";
		cout << 2*n - 4 << "\n";
		for (int i = 2; i < n; ++i) {
			cout << i << " ";
		}
		for (int i = n - 1; i > 1; i--) {
			cout << i << " ";
		}
	}
	else {
		dfs (1, -1);
		int a = 0;
		for (int i = 1; i <= n; ++i) {
			if (uzyn[a] < uzyn[i]) a = i;
 		}
 		uzyn[a] = 0;
 		par[a] = -1;
 		dfs (a, -1);
 		int b = 0;
 		for (int i = 1; i <= n; ++i) {
 			if (uzyn[b] < uzyn[i]) b = i;
		}
		int x = b;
		while (x != -1) {
			vis[x] = 1;
//			cout << x << " ";
			x = par[x];
		}
		for (int i = 1; i <= n; ++i) {
			if (vis[i]) {
				val = 0;
				barla(i, -1);
			}
		}
		if (bolonok) cout << "NO";
		else {
			cout << "YES\n";
			x = b;
			while (x != -1) {
				if (x != a and x != b) {
					jog.pb (x);
					for (int i : v[x]) {
						if (vis[i]) continue;
						if ((int)v[i].sz == 1) continue;
						jog.pb (i);
						jog.pb (x);
					}
				} 
				x = par[x];
			}
			cout << 2 * (int)jog.sz << "\n";
			for (int i : jog) cout << i << " ";
			reverse (jog.begin(), jog.end());
			for (int i : jog) cout << i << " ";
			cout << "\n";
		}
		cout << "\n";
	}
}

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