Submission #1087291

#TimeUsernameProblemLanguageResultExecution timeMemory
1087291MercubytheFirstNewspapers (CEOI21_newspapers)C++17
0 / 100
1 ms348 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; #define endl '\n' #ifdef LOCAL #include "debug.h" #else #define debug(...) 37 #endif template <typename T> void print(vector<T> v) { const int n = v.size(); for(int i = 1; i < n; ++i) { cout << i << " : " << v[i] << '\n'; } } inline void solve(){ int n, m; cin >> n >> m; if(m >= n) { cout << "NO\n"; return; } vector<vector<int> > g(n + 1); for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<int> v(n + 1, true); vector<int> sol; v[0] = false; while((int)sol.size() <= 5 * n) { int mx = 0; for(int i = 1; i <= n; ++i) { if(count_if(g[i].begin(), g[i].end(), [&](int to) { return v[to]; }) == 1) { auto it = find_if(g[i].begin(), g[i].end(), [&](int to) { return v[to]; }); assert(it != g[i].end()); if(g[*it].size() > g[mx].size()) { mx = *it; } } } if(mx == 0) { for(int i = 1; i <= n; ++i) { if(v[i] == 1 and g[i].size() > g[mx].size()) { mx = i; } } } v[mx] = false; sol.push_back(mx); vector<int> nv(n + 1); bool ok = false; for(int i = 1; i <= n; ++i) { for(int to : g[i]) { nv[i] |= v[to]; } ok |= (nv[i]); } v = nv; if(!ok) { break; } } if((int)sol.size() > 5 * n) { cout << "NO\n"; return; } cout << "YES\n" << sol.size() << "\n"; for(int x : sol) { cout << x << ' '; } cout << endl; } signed main(){ #ifdef LOCAL freopen("test.in", "r", stdin); freopen("err.txt", "w", stderr); #endif ios_base::sync_with_stdio(0); cin.tie(NULL); // signed t; cin >> t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...