Submission #1087296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087296		MercubytheFirst	Newspapers (CEOI21_newspapers)	C++17	6 / 100	9 ms	604 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[i].size() > g[mx1].size()) {
                        mx1 = *it;
                    }
                }
                else {
                    if(g[i].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;
        }
    }
    if((int)sol.size() > 5 * n) {
        assert(false);
        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();
}

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