제출 #659763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659763		fatemetmhr	Newspapers (CEOI21_newspapers)	C++17	54 / 100	64 ms	6896 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];
bool re = true;
 
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;
}

void dfs_check(int v){
    mark[v] = true;
    if(h[v] > 2)
        re = false;
    for(auto u : adj[v]) if(!mark[u]){
        h[u] = h[v] + 1;
        dfs_check(u);
    }
}
 
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);
    re = true;
    for(int i = 0; i < n; i++) if(mark[i]){
        h[i] = 0;
        dfs_check(i);
    }
    if(!re)
        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: 6 / 12
• Subtask 2: 8 / 8
• Subtask 3: 40 / 80