Submission #649825

#TimeUsernameProblemLanguageResultExecution timeMemory
6498251binNewspapers (CEOI21_newspapers)C++14
100 / 100
77 ms8208 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e3 + 5; int n, m, a, b, ix, mxd, er; vector<int> adj[NMAX], ans; void go(int x, int p, int d){ if(d > mxd){ mxd = d; ix= x; } for(int& nx : adj[x]){ if(nx == p) continue; go(nx, x, d + 1); } return; } int dfs(int x, int p){ if(x == b) return 1; int t = -1; for(int& nx : adj[x]){ if(nx == p) continue; if(dfs(nx, x)) { t = nx; break; } } if(t != -1){ ans.emplace_back(x); for(int& nx : adj[x]){ if(nx == p) continue; if(nx != t){ mxd = 0; go(nx, x, 1); if(mxd >= 3) er = 1; else if(mxd == 2) { ans.emplace_back(nx); ans.emplace_back(x); } } } } return t != -1; } int solve(){ if(n <= 2) { while(n--) ans.emplace_back(1); return 1; } mxd = -1; go(1, -1, 0); b = ix; mxd = -1; go(b, -1, 1); a = ix; dfs(adj[a][0], a); for(int i = ans.size() - 1; i >= 0; i--) ans.emplace_back(ans[i]); return !er; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < m; i++){ cin >> a >> b; adj[a].emplace_back(b); adj[b].emplace_back(a); } if(m == n - 1 && solve()) { cout << "YES\n"; cout << ans.size() << '\n'; for(int& x : ans) cout << x << ' '; } else cout << "NO"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...