Submission #659703

#	Time	Username	Problem	Language	Result	Execution time	Memory
659703		fatemetmhr	Newspapers (CEOI21_newspapers)	C++17	8 / 100	3 ms	2772 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define fi     first
#define se     second
#define all(x) x.begin(), x.end()

const int maxn5 = 1e5 + 10;

vector <int> adj[maxn5], av;
bool mark[maxn5];
int h[maxn5];

void dfs(int v, int par){
    for(auto u : adj[v]) if(u != par){
        h[u] = h[v] + 1;
        dfs(u, v);
    }
}

bool dfs_set_mark(int v, int w, int par){
    if(v == w){
        av.pb(w);
        mark[w] = true;
        return true;
    }
    bool re = false;
    for(auto u : adj[v]) if(u != par){
        re |= dfs_set_mark(u, w, v);
    }
    if(re){
        mark[v] = true;
        av.pb(v);
    }
    return re;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    if(m != n - 1){
        return cout << "NO" << endl, 0;
    }
    dfs(0, -1);
    int d1 = 0;
    for(int i = 0; i < n; i++) if(h[i] > h[d1])
        d1 = i;
    h[d1] = 0;
    dfs(d1, -1);
    int d2 = 0;
    for(int i = 0; i < n; i++) if(h[i] > h[d2])
        d2 = i;
    dfs_set_mark(d1, d2, -1);
    for(int i = 0; i < n; i++) if(!mark[i] && adj[i].size() > 1)
        return cout << "NO\n", 0;
    cout << "YES\n";
    //cout << "its " << d1 << ' ' << d2 << endl;
    n = av.size();
    if(n == 1){
        return cout << 1 << '\n' << av[0] + 1 << endl, 0;
    }
    if(n == 2){
        return cout << 2 << '\n' << av[0] + 1 << ' ' << av[0] + 1 << endl, 0;
    }
    cout << 2 * (n - 2) << endl;
    for(int i = 1; i < n - 1; i++)
        cout << av[i] + 1 << ' ';
    for(int i = n - 2; i >= 1; i--)
        cout << av[i] + 1 << ' ';
    cout << endl;
}

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