Submission #1187214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187214		Unforgettablepl	Newspapers (CEOI21_newspapers)	C++20	8 / 100	1 ms	584 KiB

newspapers

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,M;
    cin >> n >> M;
    if(M!=n-1){
        cout << "NO\n";
        return 0;
    }
    vector<vector<int>> adj(n+1);
    for(int i=1;i<=M;i++){
        int u,v;cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    pair<int,int> ans = {0,0};
    int p1 = 0;
    int p2 = 0;
    {
        vector<int> subsize(n+1);
        function<int(int,int)> subsizeDFS = [&](int x,int p){
            subsize[x]=1;
            for(int&i:adj[x])if(i!=p)subsize[x]+=subsizeDFS(i,x);
            return subsize[x];
        };
        function<void(int,int,int)> dfs = [&](int x,int p,int dist){
            if(ans.first<dist)ans={dist,x};
            sort(adj[x].rbegin(),adj[x].rend(),[&](const int &a,const int &b){return subsize[a]<subsize[b];});
            for(int&i:adj[x])if(i!=p)dfs(i,x,dist+1);
        };
        subsizeDFS(1,0);
        dfs(1,0,1);
        p1 = ans.second;
        ans = {0,0};
        subsize = vector<int>(n+1);
        subsizeDFS(p1,0);
        dfs(p1,0,1);
        p2 = ans.second;
        ans = {0,0};
        subsize = vector<int>(n+1);
        subsizeDFS(p2,0);
        dfs(p2,0,1);
        p1 = ans.second;
    }
    vector<bool> isOnDia(n+1);
    {
        function<bool(int,int)> dfs = [&](int x,int p){
            if(x==p2){isOnDia[x]=true;return true;}
                for(int&i:adj[x])if(i!=p)if(dfs(i,x)){isOnDia[x]=true;return true;}
            return false;
        };
        dfs(p1,0);
    }
    bool works = true;
    vector<int> walk;
    {
        function<void(int,int)> generateDFS = [&](int x,int p){
            if(!isOnDia[x]){
                if(!isOnDia[p]){
                    if(adj[x].size()>1)works=false;
                    return;
                }
                if(adj[x].size()==2){
                    walk.emplace_back(x);
                    walk.emplace_back(p);
                } else if(adj[x].size()>2)works=false;
                for(int&i:adj[x])if(i!=p)generateDFS(i,x);
                return;
            }
            if(x!=p1 and x!=p2)walk.emplace_back(x);
            for(int&i:adj[x])if(!isOnDia[i])generateDFS(i,x);
            for(int&i:adj[x])if(i!=p and isOnDia[i])generateDFS(i,x);
        };
        generateDFS(p1,0);
    }
    vector<int> revWalk = walk;
    reverse(revWalk.begin(),revWalk.end());
    for(int&i:revWalk)walk.emplace_back(i);
    if(n<=2)walk.emplace_back(1);
    if(n==2)walk.emplace_back(1);
    if(works){
        cout << "YES\n";
        cout << walk.size() << '\n';
        for(int&i:walk)cout<<i<<' ';
        cout << '\n';
    } else cout << "NO\n";
}

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