Submission #659778

#	Time	Username	Problem	Language	Result	Execution time	Memory
659778		fatemetmhr	Newspapers (CEOI21_newspapers)	C++17	100 / 100	78 ms	6828 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, out;
bool mark[maxn5], good[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);
    for(int i = 0; i < n; i++) if(mark[i])
        good[i] = true;
    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;
    int cnt = av.size();
    if(cnt == 1){
        return cout << 1 << '\n' << av[0] + 1 << endl, 0;
    }
    if(cnt == 2){
        return cout << 2 << '\n' << av[0] + 1 << ' ' << av[0] + 1 << endl, 0;
    }
    for(int i = 0; i < n; i++)
        mark[i] = good[i];
    int id = 1;
    while(id < av.size() - 1){
        out.pb(av[id]);
        for(auto u : adj[av[id]]) if(adj[u].size() > 1 && !mark[u]){
            out.pb(u);
            out.pb(av[id]);
        }
        id++;
    }
    cout << out.size() * 2 << endl;
    for(auto u : out)
        cout << u + 1 << ' ';
    while(out.size()){
        cout << out.back() + 1 << ' ';
        out.pop_back();
    }
    cout << endl;
}

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:97:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     while(id < av.size() - 1){
      |           ~~~^~~~~~~~~~~~~~~

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