Submission #576717

#TimeUsernameProblemLanguageResultExecution timeMemory
576717talant117408Diversity (CEOI21_diversity)C++17
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' void solve() { int n, m; cin >> n >> m; vector <vector <int>> graph(n+1); vector <int> used(n+1), color(n+1, -1); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; graph[a].pb(b); graph[b].pb(a); } int flag = 0; function<void(int, int, int)> dfs = [&](int v, int p, int c) { used[v] = 1; if (color[v] == -1) color[v] = c; for (auto to : graph[v]) { if (used[to]) { if (used[to] == 1 && to != p) { flag = 1; } continue; } dfs(to, v, 1-c); } used[v] = 2; }; dfs(1, 1, 1); for (int i = 1; i <= n; i++) { int cnt = 0; for (auto to : graph[i]) { if (sz(graph[to]) == 1) continue; auto x = graph[to][0]; if (x == i) x = graph[to][1]; if (sz(graph[x]) > 1) cnt++; } if (cnt > 2) flag = 1; } if (flag) { cout << "NO" << endl; return; } int forbidden, start = 1, forbidden_leaves = 0; for (int i = 1; i <= n; i++) { if (sz(graph[i]) == 1) { start = graph[i][0]; forbidden = color[i]; break; } } for (int i = 1; i <= n; i++) { if (sz(graph[i]) == 1 && forbidden == color[i]) { forbidden_leaves++; } } set <int> visited; vector <int> order; int add = 1; function <void(int, int)> dfs2 = [&](int v, int p) { if (add) { visited.insert(v); order.pb(v); } if (sz(visited) == n-forbidden_leaves) { add = 0; } for (auto to : graph[v]) { if (to == p) continue; if (sz(graph[to]) == 1 && color[to] == forbidden) continue; dfs2(to, v); if (add) { visited.insert(v); order.pb(v); } } }; dfs2(start, start); cout << "YES" << endl; cout << sz(order)*2 << endl; for (auto to : order) cout << to << ' '; for (auto to : order) cout << to << ' '; } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...