Submission #1155090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155090		ace5	Newspapers (CEOI21_newspapers)	C++20	4 / 100	1 ms	584 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
bool cyc = 0;
vector<int> vis;

void dfs1(int v,int p)
{
    vis[v] = 1;
    for(auto u:g[v])
    {
        if(!vis[u])
            dfs1(u,v);
        else if(u != p)
            cyc = 1;
    }
    return ;
}
pair<int,int> dfs2(int v,int p)
{
    pair<int,int> ans  ={v,0};
    for(auto u:g[v])
    {
        if(u != p)
        {
            pair<int,int> ne = dfs2(u,v);
            if(ne.second + 1 > ans.second)
            {
                ans = {ne.first,ne.second+1 };
            }
        }
    }
    return ans;
}
vector<int> path;

bool dfs3(int v,int p,int to)
{
    path.push_back(v);
    if(v == to)
    {
        return true;
    }
    for(auto u:g[v])
    {
        if(u != p)
        {
            if(dfs3(u,v,to))
                return true;
        }
    }
    path.pop_back();
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    g.resize(n);
    vis.resize(n);
    for(int j = 0;j < m;++j)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(0,-1);
    if(cyc)
    {
        cout << "NO\n";
        return 0;
    }
    else
    {
        int st = dfs2(0,-1).first;
        int fn = dfs2(st,-1).first;
        dfs3(st,-1,fn);
        vector<bool> isin(n);
        for(int j = 0;j < path.size();++j)
        {
            isin[j] = 1;
        }
        int no = 0;
        for(int j = 0;j < n;++j)
        {
            if(!isin[j])
            {
                if(g[j].size() != 1)
                {
                    for(auto u:g[j])
                    {
                        if(!isin[u] && g[u].size() > 1)
                        {
                            no = 1;
                        }
                    }
                }
            }
        }
        if(no)
        {
            cout << "NO\n";
        }
        else
        {
            cout << "YES\n";
            if(n == 1)
            {
                cout << "1\n1";
                return 0;
            }
            else if(n == 2)
            {
                cout << "2\n1 1\n";
                return 0;
            }
            vector<int> ans;
            for(int i = 1;i+1 < path.size();++i)
            {
                ans.push_back(path[i]);
                for(auto u:g[path[i]])
                {
                    if(!isin[u] && g[u].size() > 1)
                    {
                        ans.push_back(u);
                        ans.push_back(path[i]);
                    }
                }
            }
            for(int j = 1-(path.size()%2);j+1 < path.size();++j)
                ans.push_back(path[j]);
            cout << ans.size() << "\n";
            for(auto c:ans)
                cout << c+1 << ' ';
        }
    }
}

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