Submission #1126121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126121		TrieTr	Newspapers (CEOI21_newspapers)	C++20	8 / 100	30 ms	23880 KiB

newspapers

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

void local() {
	#define taskname ""
	if(fopen(taskname".inp", "r")) {
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template <class X, class Y> bool mini(X& x, Y y) {return x > y ? x = y, true : false;}
template <class X, class Y> bool maxi(X& x, Y y) {return x < y ? x = y, true : false;}

const int N = 1e6 + 5;

int n, m;
vector<int> adj[N];
vector<int> ve;
vector<int> res;

int sz[N];
void pre_dfs(int u, int p = -1) {
	sz[u] = 1;
	for(int& v : adj[u]) {
		if(v == p) continue;
		pre_dfs(v, u);
		sz[u] += sz[v];
	}
}
bool dfs(int u, int p = -1) {
	ve.emplace_back(u);
	int cnt = 0, cnt1 = 0;
	for(int& v : adj[u]) {
		if(v == p) continue;
		if(sz[v] > 1) cnt++;
		else cnt1++;
	}
	if(cnt > 1) return false;
	//if(cnt1 > 0 && p != -1) ve.emplace_back(u);
	for(int& v : adj[u]) {
		if(v == p) continue;
		if(sz[v] > 1) return dfs(v, u);
	}
	//if(cnt1 > 0 && p != -1) ve.pop_back();
	return true;
}

int main() {
	fastio; local();
	cin >> n >> m;
	if(m > n - 1) return cout << "NO", 0;
	for(int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		adj[u].emplace_back(v); adj[v].emplace_back(u);
	}

	if(n <= 2) {
		cout << "YES\n" << n << '\n';
		for(int i = 1; i <= n; i++) cout << 1 << ' ';
		cout << '\n';
		return 0;
	}

	for(int i = 1; i <= n; i++) {
		pre_dfs(i);
		ve.clear();
		if(dfs(i)) {
			//cout << i << ' ' << ve.size() << '\n';
			// if(i == 1) {
			// 	for(int& val : ve) cout << val << ' ';
			// 	cout << '\n';
			// }
			if(res.empty() || ve.size() < res.size()) swap(res, ve);
		}
	}
	if(res.empty()) cout << "NO";
	else {
		cout << "YES\n";
		cout << res.size() * 2 << '\n';
		for(int& val : res) cout << val << ' ';
		reverse(res.begin(), res.end());
		for(int& val : res) cout << val << ' ';
	}
}

Compilation message (stderr)

newspapers.cpp: In function 'void local()':
newspapers.cpp:7:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
newspapers.cpp:8:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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