Submission #589530

#	Time	Username	Problem	Language	Result	Execution time	Memory
589530		jasmin	Newspapers (CEOI21_newspapers)	C++14	50 / 100	67 ms	12288 KiB

newspapers

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

int bfs(int n, vector<vector<int> >& adi){
    vector<bool> vis(n);
    deque<int> q;
    q.push_back(0);
    int last=0;
    vis[0]=true;
    while(!q.empty()){
        int v=last=q.front();
        q.pop_front();

        for(auto u: adi[v]){
            if(!vis[u]){
                vis[u]=true;
                q.push_back(u);
            }
        }
    }
    return last;
}

vector<int> a;
int dfs(int v, int hight, vector<bool>& vis, vector<vector<int> >& adi, bool& pos){
    if(vis[v]){
        return 0;
    }
    vis[v]=true;
    int depth=1;

    if(adi[v].size()>1){
        a.push_back(v);
    }

    int further=0;
    for(auto u: adi[v]){

        int subtree=dfs(u, hight+1, vis, adi, pos);
        depth=max(depth, subtree+1);
        if(subtree>2){
            further++;
        }
        else if(subtree==2 && adi[v].size()>2){
            a.push_back(v);
        }
        
    }
    pos=pos && (further<=1);
    return depth;
}

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

    int n, m;
    cin >> n >> m;
    vector<vector<int> > adi(n);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        adi[a-1].push_back(b-1);
        adi[b-1].push_back(a-1);
    }

    bool pos=(m==n-1);
    int root=bfs(n, adi);
    
    vector<bool> vis(n, false);
    dfs(root, 0, vis, adi, pos);

    if(pos){
        cout << "YES\n";
        if(n==1){
            cout << 1 << "\n" << 1 << "\n";
            return 0;
        }
        else if(n==2){
            cout << 2 << "\n" << 1 << " " << 2 << "\n";
            return 0;
        }
        cout << 2*a.size()<< "\n";
        for(int i=0; i<(int)a.size(); i++){
            cout << i+1 << " ";
        }
        for(int i=a.size()-1; i>=0; i--){
            cout << i+1 << " ";
        }
        cout << "\n";
    }
    else{
        cout << "NO\n";
    }
}

• Subtask 1: 6 / 12
• Subtask 2: 4 / 8
• Subtask 3: 40 / 80