Submission #859563

#	Time	Username	Problem	Language	Result	Execution time	Memory
859563		Tenis0206	Newspapers (CEOI21_newspapers)	C++11	100 / 100	49 ms	4688 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1000;

int n,m;

vector<int> G[nmax + 5];

vector<int> lst;

bool ok = true;

int l[nmax + 5], Max[nmax + 5];

int start = 0;

void verif(int nod, int dad = 0)
{
    l[nod] = 1;
    Max[nod] = 0;
    int nr_big = 0;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        verif(it,nod);
        if(l[it] + 1 > l[nod])
        {
            l[nod] = l[it] + 1;
            Max[nod] = it;
        }
        if(l[it] > 2)
        {
            ++nr_big;
        }
    }
    if(nr_big > 1)
    {
        ok = false;
    }
}

void dfs(int nod, int dad = 0)
{
    if(G[nod].size()==1 && nod!=start)
    {
        return;
    }
    lst.push_back(nod);
    for(auto it : G[nod])
    {
        if(it==dad || it==Max[nod])
        {
            continue;
        }
        if(l[it]==1)
        {
            continue;
        }
        lst.push_back(it);
        lst.push_back(nod);
    }
    dfs(Max[nod],nod);
    lst.push_back(nod);
    for(auto it : G[nod])
    {
        if(it==dad || it==Max[nod])
        {
            continue;
        }
        if(l[it]==1)
        {
            continue;
        }
        lst.push_back(it);
        lst.push_back(nod);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    if(m != n - 1)
    {
        cout<<"NO"<<'\n';
        return 0;
    }
    if(n==1)
    {
        cout<<"YES"<<'\n';
        cout<<1<<'\n';
        cout<<1<<'\n';
        return 0;
    }
    vector<int> rez;
    for(start=1;start<=n;start++)
    {
        ok = true;
        verif(start);
        if(!ok)
        {
            continue;
        }
        lst.clear();
        dfs(start);
        if(lst.size() < rez.size() || !rez.size())
        {
            rez = lst;
        }
    }
    if(!rez.size())
    {
        cout<<"NO"<<'\n';
    }
    else
    {
        cout<<"YES"<<'\n';
        cout<<rez.size()<<'\n';
        for(auto it : rez)
        {
            cout<<it<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

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