Submission #1087370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087370		MercubytheFirst	Newspapers (CEOI21_newspapers)	C++17	6 / 100	12 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;
            }
        }
        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