Submission #576904

#TimeUsernameProblemLanguageResultExecution timeMemory
576904tengiz05Newspapers (CEOI21_newspapers)C++17
100 / 100
2 ms480 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; int main() { int n, m; cin >> n >> m; if (n == 1) { cout << "YES\n"; cout << "1\n"; cout << "1\n"; return 0; } if (n == 2) { cout << "YES\n"; cout << "2\n"; cout << "1 1\n"; return 0; } if (m >= n) { cout << "NO\n"; return 0; } vector<vector<int>> adj(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } vector<int> dep(n); pair<int, int> mx{-1, -1}; function<void(int, int)> dfs = [&](int u, int p) { mx = max(mx, pair(dep[u], u)); for (int v : adj[u]) { if (v != p) { dep[v] = dep[u] + 1; dfs(v, u); } } }; dfs(0, -1); int last = mx.second; mx = {-1, -1}; dep[last] = 0; dfs(last, -1); int u = mx.second; vector<int> g; function<bool(int, int)> dfs2 = [&](int u, int p) { if (u == last) { g.push_back(u); return true; } for (int v : adj[u]) { if (v != p && dfs2(v, u)) { g.push_back(u); return true; } } return false; }; dfs2(u, -1); int p = g.size() / 2; u = g[p]; int l = -1, r = -1; if (p > 0) { l = g[p - 1]; } if (p < int(g.size()) - 1) { r = g[p + 1]; } vector<int> mxdep(n), par(n); dfs = [&](int u, int p) { par[u] = p; mxdep[u] = u; for (int v : adj[u]) { if (v != p) { dep[v] = dep[u] + 1; dfs(v, u); if (dep[mxdep[v]] > dep[mxdep[u]]) { mxdep[u] = mxdep[v]; } } } }; dep[u] = 0; dfs(u, -1); for (int i = 0; i < n; i++) { int c = 0; for (int v : adj[i]) { if (dep[mxdep[v]] - dep[i] >= 3) { c++; } } if (c >= 3) { cout << "NO\n"; return 0; } } std::vector<int> a; int s = adj[last][0]; for (int &v : adj[u]) { if (v == l) { swap(v, adj[u][0]); } if (v == r) { swap(v, adj[u].back()); } } dfs(u, -1); int lst = -1; sort(g.begin(), g.end()); dfs = [&](int u, int p) { a.push_back(u); lst = u; for (int v : adj[u]) { if (v != p && adj[v].size() > 1 && !binary_search(g.begin(), g.end(), v)) { dfs(v, u); a.push_back(u); } } for (int v : adj[u]) { if (v != p && adj[v].size() > 1 && binary_search(g.begin(), g.end(), v)) { dfs(v, u); a.push_back(u); } } }; dfs(s, -1); while (a.back() != lst) a.pop_back(); cout << "YES\n"; cout << 2 * a.size() << "\n"; for (int x : a) { cout << x + 1 << " "; } reverse(a.begin(), a.end()); for (int x : a) { cout << x + 1 << " "; } cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...