oj.uz

Submission #1087371

# Submission time Handle Problem Language Result Execution time Memory
1087371 2024-09-12T14:44:56 Z MercubytheFirst Newspapers (CEOI21_newspapers) C++17
6 / 100
 8 ms 348 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 0 ms 348 KB Provide a successful but not optimal strategy.
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
6.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Partially correct 0 ms 348 KB Provide a successful but not optimal strategy.
7 Correct 1 ms 348 KB Output is correct
8 Partially correct 0 ms 348 KB Provide a successful but not optimal strategy.
9 Correct 0 ms 348 KB Output is correct
10 Partially correct 0 ms 348 KB Provide a successful but not optimal strategy.
11 Partially correct 7 ms 348 KB Provide a successful but not optimal strategy.
12 Correct 2 ms 348 KB Output is correct
13 Partially correct 3 ms 348 KB Provide a successful but not optimal strategy.
14 Partially correct 3 ms 348 KB Provide a successful but not optimal strategy.
15 Correct 4 ms 348 KB Output is correct
16 Partially correct 7 ms 348 KB Provide a successful but not optimal strategy.
17 Correct 7 ms 344 KB Output is correct
18 Partially correct 7 ms 348 KB Provide a successful but not optimal strategy.
19 Correct 8 ms 348 KB Output is correct
20 Partially correct 7 ms 344 KB Provide a successful but not optimal strategy.

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 0 ms 348 KB Provide a successful but not optimal strategy.
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -