Submission #652521

#	Time	Username	Problem	Language	Result	Execution time	Memory
652521		kinope	Newspapers (CEOI21_newspapers)	C++17	100 / 100	102 ms	8092 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e3+10;
vector<int> g[maxn];
int ojc[maxn], ojc2[maxn], d[maxn], gle[maxn];

void dfs(int x, int o, int odl){
		for(int u : g[x]) if(u != o) dfs(u, x, odl + 1);
		ojc[x] = o; d[x] = odl;
}

void dfsG(int x, int o){
		for(int u : g[x]) if(u != o){
				dfsG(u, x);
				gle[x] = max(gle[x], gle[u]);}
		++gle[x];
}

int main(){
		
		int n, m, a, b;
		scanf("%d%d", &n, &m);
		
		for(int i = m+1; --i; ){
				scanf("%d%d", &a, &b);
				g[a].emplace_back(b);
				g[b].emplace_back(a);
		}
		if(m != n-1){ printf("NO"); return 0; }
		
		int X=1, Y=1, odl = 0;
		dfs(1, 0, 0);
		for(int i = 1; i <= n; ++i) if(d[i] > odl) X = i, odl = d[i];
		dfs(X, 0, 0);
		odl = 0;
		for(int i = 1; i <= n; ++i) if(d[i] > odl) Y = i, odl = d[i];
		dfsG(Y, 0);
		
		vector<int> ans;
		if(n <= 2) while(n--) ans.emplace_back(1);
		
		for(int x = Y; x; x = ojc[x]){
				ojc2[ojc[x]] = x;
				if(x == X || x == Y) continue;
				ans.emplace_back(x);
				for(int u : g[x]) if(u != ojc[x] && u != ojc2[x]){
						if(gle[u] > 2) { printf("NO"); return 0; }
						else if(gle[u] == 1) continue;
						ans.emplace_back(u);
						ans.emplace_back(x);
				}
				
		}
		
		for(int x = X; x; x = ojc2[x]){
				if(x == X || x == Y) continue;
				ans.emplace_back(x);
				for(int u : g[x]) if(u != ojc[x] && u != ojc2[x]){
						if(gle[u] == 1) continue;
						ans.emplace_back(u);
						ans.emplace_back(x);
				}
				//printf("%d ", x);
		}
		
		printf("YES\n%d\n", (int) ans.size());
		for(int u : ans) printf("%d ", u);
		
		return 0;
}

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
newspapers.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~

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