Submission #1008407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008407		cow123	Newspapers (CEOI21_newspapers)	C++14	60 / 100	3 ms	648 KiB

newspapers

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb emplace_back
using namespace std;
const int maxn = 1005;
vector<int> V[maxn],odp;
int vis[maxn],vis1[maxn],mark[maxn];
void dfs(int v){
    for(auto y : V[v]){
        if(mark[y] == 0 && vis[y] == 0 && V[y].size() > 1){
            vis[y] = 1;
            odp.pb(y);
            odp.pb(v);            
        }
    }
    for(auto y : V[v]){
        if(mark[y] == 1 && vis[y] == 0){
            vis[y] = 1;
            odp.pb(y);
            dfs(y);
        }
    }
}
int d1 = 0;
void dyst(int v){
    for(auto y : V[v]){
        if(vis[y] == 0){
            vis[y] = vis[v] + 1;
            d1 = max(d1,vis[y]);
            dyst(y);
            
        }
    }
}
int main(){
    int n,m;
    cin>>n >>m;
    if(m > n - 1){ //cykl
        cout<<"NO";
        return 0;
    }
    if(n == 1){
        cout<<"YES" <<"\n" <<1 <<"\n" <<1;
        return 0;
    }
    if(n == 2){
        cout<<"YES" <<"\n" <<2 <<"\n" <<1 <<" " <<1;
        return 0;
    }
    
    FOR(i,0,m){
        int x,y;
        cin>>x >>y;
        V[x].pb(y);
        V[y].pb(x);
    }
    FOR(i,1,n + 1){
        if(V[i].size() >= 3){
            FOR(j,0,n + 1){
                vis[j] = 0; 
            }
            vis[i] = 1;
            int cnt = 0;
            for(auto y : V[i]){
                vis[y] = 1;
                  d1 = 0;
                  dyst(y);
                if(d1 >= 3){
                    ++cnt;
                } 
            }
            if(cnt >= 3){ 
                cout<<"NO";
                return 0;
            }
        }
    }
    
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    d1 = 0;
    int y1 = 0;
    vis[1] = 1;
    dyst(1);
    FOR(i,1,n + 1){
        if(vis[i] == d1){
            y1 = i;
        }
    
    }
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    d1 = 0;
    vis[y1] = 1;
    dyst(y1);
    FOR(i,1,n + 1){
        if(vis[i] == d1){
            y1 = i;
        }
    }
    FOR(i,0,n + 1){
        vis1[i] = vis[i];
        vis[i] = 0;
    }
    d1 = 0;
    vis[y1] = 1;
    dyst(y1);
    int x2 = 0;
    FOR(i,0,n + 1){
        if(vis[i] + vis1[i] == d1 + 1 && V[i].size() > 1){
            mark[i] = 1;
        }
    }
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    FOR(i,0,n + 1){
        if(V[i].size() > 1 && mark[i] == 1){
            x2 = i;
        }
    }
    odp.pb(x2);
    vis[x2] = 1;
    dfs(x2);
    cout<<"YES" <<"\n" <<odp.size() * 2 <<"\n";
    for(auto y : odp){
        cout<<y <<" ";
    }
    for(int i = odp.size() - 1; i >= 0;--i){
        cout<<odp[i] <<" ";
    } 
}

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