Submission #1087371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087371		MercubytheFirst	Newspapers (CEOI21_newspapers)	C++17	6 / 100	8 ms	348 KiB

newspapers

#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';
    }cout << "\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);
    }
    assert(g[0].empty());
    vector<int> v(n + 1, true);
    vector<int> sol;
    v[0] = false;
    while((int)sol.size() <= 5 * n) {
        int mx1 = 0, mx2 = 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(v[i]) {
                    if(g[*it].size() > g[mx1].size()) {
                        mx1 = *it;
                    }
                }
                else {
                    if(g[*it].size() > g[mx2].size()) {
                        mx2 = *it;
                    }
                }
            }
        }
        int mx = (mx1 == 0 ? mx2 : mx1);
        if(mx == 0) {
            for(int i = 1; i <= n; ++i) {
                if(v[i] == 1 and g[i].size() >= g[mx].size()) {
                    mx = i;
                }
            }
        }
        assert(mx != 0);
        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]);
        }
        // cout << mx << "\n";
        // print(nv);
        v = nv;
        if(!ok) {
            break;
        }
    }
    while(sol.size() > 5 * n) {
        sol.pop_back();
    }
    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();
}

Compilation message (stderr)

newspapers.cpp: In function 'void solve()':
newspapers.cpp:82:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     while(sol.size() > 5 * n) {
      |           ~~~~~~~~~~~^~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 6 / 8
• Subtask 3: 0 / 80