oj.uz

Submission #859554

# Submission time Handle Problem Language Result Execution time Memory
859554 2023-10-10T10:11:37 Z Tenis0206 Newspapers (CEOI21_newspapers) C++11
0 / 100
 297 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e3;

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;
    }
    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
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -