oj.uz

Submission #717776

# Submission time Handle Problem Language Result Execution time Memory
717776 2023-04-02T13:56:54 Z baokhue232005 Newspapers (CEOI21_newspapers) C++14
6 / 100
 1 ms 468 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 1005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

void die(){
    cout << "NO\n"; exit(0);
}

void real_win(vi cac){
    vi seap = cac;
    if(cac.size() % 2 == 0) cac.pb(1);
    for(int cc : seap) cac.pb(cc);
    cout << "YES\n";
    cout << cac.size() << endl;
    for(int cc : cac) cout << cc << " ";
    cout << endl;
    exit(0);
}

vi best;
int cnt_best = oo;

void win(vi cac){
    if(cac.size() < cnt_best){
        best = cac;
        cnt_best = cac.size();
    }
}
int sub[maxN];
vi vc[maxN];

void dfs_sub(int node, int par){
    sub[node] = 1;
    for(int cc : vc[node]) if(cc != par){
        dfs_sub(cc, node);
        sub[node] += sub[cc];
    }
}

void solve(int root){
    dfs_sub(root, 0);
    while(1){
        bool saved = 0;
        for(int cc : vc[root]){
            if(sub[cc] < sub[root] && sub[cc] > 1){
                root = cc;
                saved = 1;
                break;
            }
        }
        if(!saved) break;
    }
    dfs_sub(root, 0);
    vi ans;
    ans.pb(root);
    while(1){
        if(vc[root].empty()) break;
        int node = vc[root].back(); vc[root].pop_back();
        if(sub[node] > sub[root] || sub[node] == 1) continue;
        if(vc[root].empty()){
            root = node;
            ans.pb(node);
            continue;
        }
        // actual child; spare node inside
        if(sub[node] > 2) swap(node, vc[root][0]);
        if(sub[node] <= 2){
            ans.pb(node);
            ans.pb(root);
            continue;
        }
        return;
    }
    win(ans);
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> z;
    if(z >= n) die();
    if(n == 1){
        cout << "YES\n1\n1\n"; exit(0);
    }
    for1(i, 2, n){
        cin >> x >> y;
        vc[x].pb(y);
        vc[y].pb(x);
    }
    solve(1);
    if(cnt_best != oo) real_win(best);
    die();
}

Compilation message

newspapers.cpp: In function 'void win(std::vector<long long int>)':
newspapers.cpp:50:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   50 |     if(cac.size() < cnt_best){
      |        ~~~~~~~~~~~^~~~~~~~~~

Subtask #1
0.0 / 12.0

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

Subtask #2
6.0 / 8.0

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

Subtask #3
0.0 / 80.0

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