Submission #624681

#TimeUsernameProblemLanguageResultExecution timeMemory
624681iomoon191Newspapers (CEOI21_newspapers)C++17
100 / 100
1 ms468 KiB
#include <bits/stdc++.h> using ll = long long; #define int ll using namespace std; #define sz(x) (int)(x).size() #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, l, r) for(int i = l; i >= r; i--) #define fi first #define se second #define mod 998244353 #define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n" using vi = vector<int>; using pi = pair<int, int>; const ll N = 1005; const ll inf = 1e18; int n, m, par[N]; vi adj[N]; bool ok[N], used[N]; pi dfs(int u, int p = -1){ pi res(0, u); for(auto &i : adj[u]){ if(i == p) continue; par[i] = u; pi j = dfs(i, u); j.fi++; res = max(res, j); } return res; } void solve(){ cin >> n >> m; if(n == 1){ cout << "YES\n1\n1"; return; } if(n == 2){ cout << "YES\n2\n1 1"; return; } if(m != n - 1){ cout << "NO"; return; } foru(i, 1, m){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int x = dfs(1).se; int y = dfs(x).se; for(int i = y; ; i = par[i]){ ok[i] = true; used[i] = true; for(auto &j : adj[i]){ ok[j] = true; for(auto &k : adj[j]){ ok[k] = true; } } if(i == x) break; } if(count(ok + 1, ok + n + 1, 0)){ cout << "NO"; return; } vi res; for(int i = par[y]; i != x; i = par[i]){ res.push_back(i); for(auto &j : adj[i]){ if(used[j] or sz(adj[j]) == 1){ continue; } res.push_back(j); res.push_back(i); } } cout << "YES\n" << (sz(res) << 1) << "\n"; foru(i, 0, sz(res) - 1) cout << res[i] << " "; ford(i, sz(res) - 1, 0) cout << res[i] << " "; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...