Submission #613977

#TimeUsernameProblemLanguageResultExecution timeMemory
613977yuto1115Newspapers (CEOI21_newspapers)C++17
100 / 100
64 ms4584 KiB
#include <bits/stdc++.h> #define rep(i, n) for(ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i) #define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i) #define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i) #define pb push_back #define eb emplace_back #define all(a) a.begin(), a.end() #define SZ(a) int(a.size()) using namespace std; using ll = long long; using P = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vp = vector<P>; using vvp = vector<vp>; using vb = vector<bool>; using vvb = vector<vb>; using vs = vector<string>; const int inf = 1001001001; const ll linf = 1001001001001001001; template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } vi solve2(int n, vvi G) { if (n == 1) return {1}; if (n == 2) return {1, 1}; auto dfs = [&](auto &dfs, int u, int p) -> vi { vi res; for (int v: G[u]) { if (v == p) continue; vi now = dfs(dfs, v, u); if (SZ(now) > SZ(res)) res = now; } res.pb(u); return res; }; int a = dfs(dfs, 0, -1)[0]; vi dm = dfs(dfs, a, -1); vi res; rep2(i, 1, SZ(dm) - 1) { res.pb(dm[i] + 1); for (int j: G[dm[i]]) { if (j == dm[i - 1] or j == dm[i + 1]) continue; vi now = dfs(dfs, j, dm[i]); if (SZ(now) >= 3) return {}; if (SZ(now) == 2) { res.pb(now.back() + 1); res.pb(dm[i] + 1); } } } vi rev = res; reverse(all(rev)); res.insert(res.end(), all(rev)); return res; } vi solve(int n, vvi G) { if (n == 1) return {1}; assert(n <= 20); vi d(1 << n, inf); vp pre(1 << n); queue<int> q; d[(1 << n) - 1] = 0; q.push((1 << n) - 1); while (not q.empty()) { int now = q.front(); q.pop(); int nx = 0; rep(i, n) { for (int j: G[i]) { if (now >> j & 1) nx |= 1 << i; } } rep(i, n) { if (~nx >> i & 1) continue; nx -= 1 << i; if (chmin(d[nx], d[now] + 1)) { q.push(nx); pre[nx] = {now, i}; } nx += 1 << i; } } if (d[0] == inf) return {}; vi ans; int now = 0; while (now < (1 << n) - 1) { ans.pb(pre[now].second + 1); now = pre[now].first; } reverse(all(ans)); return ans; } random_device seed_gen; mt19937 engine(seed_gen()); int rnd(int mn, int mx) { uniform_int_distribution<int> dist(mn, mx); return dist(engine); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); // int n; // cin >> n; // rep(_, 10000) { // vvi G(n); // rep2(i, 1, n) { // int j = rnd(0, i - 1); // G[i].pb(j); // G[j].pb(i); // } // if (solve(n, G).empty() != solve2(n, G).empty()) { // cout << "#" << endl; // rep(i, n) { // for (int j: G[i]) { // if (i < j) { // cout << i << ' ' << j << endl; // } // } // } // } // } int n, m; cin >> n >> m; vvi G(n); rep(i, m) { int u, v; cin >> u >> v; --u, --v; G[u].pb(v); G[v].pb(u); } if (m > n - 1) { cout << "NO" << endl; return 0; } vi ans = solve2(n, G); if (ans.empty()) { cout << "NO" << endl; return 0; } cout << "YES" << endl; cout << SZ(ans) << endl; rep(i, SZ(ans)) cout << ans[i] << (i < SZ(ans) - 1 ? ' ' : '\n'); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...