Submission #552964

#	Time	Username	Problem	Language	Result	Execution time	Memory
552964		ToroTN	Newspapers (CEOI21_newspapers)	C++14	100 / 100	85 ms	12080 KiB

newspapers

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n,m,u_i[1000005],v_i[1000005],id[1005],st,lv[1005],mx,ed;
int par[1005],num,hsh[1005],type=0;
vector<int> v[1005],g[1005],line,ans;
stack<int> stk;
void dfs(int u,int p)
{
    for(auto node:g[u])
    {
        if(node!=p)
        {
            lv[node]=lv[u]+1;
            dfs(node,u);
        }
    }
}

void dfs2(int u,int p)
{
    for(auto node:g[u])
    {
        if(node!=p)
        {
            par[node]=u;
            lv[node]=lv[u]+1;
            dfs2(node,u);
        }
    }
}

void dfs3(int u,int p)
{
    ans.pb(u);
    for(auto node:g[u])
    {
        if(p!=node&&hsh[node]==0)
        {
            lv[node]=lv[u]+1;
            if(lv[node]==2)type=-1;
            dfs3(node,u);
            ans.pb(u);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u_i[i],&v_i[i]);
        ++id[u_i[i]];
        ++id[v_i[i]];
        v[u_i[i]].pb(v_i[i]);
        v[v_i[i]].pb(u_i[i]);
    }
    if(n==1)
    {
        printf("YES\n1\n1\n");
        return 0;
    }
    if(n==2)
    {
        printf("YES\n2\n1 1\n");
        return 0;
    }
    if(m>n-1)
    {
        printf("NO\n");
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        if(id[u_i[i]]>1&&id[v_i[i]]>1)
        {
            g[u_i[i]].pb(v_i[i]);
            g[v_i[i]].pb(u_i[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(id[i]>1)
        {
            lv[i]=1;
            dfs(i,i);
            mx=-1;
            for(int j=1;j<=n;j++)
            {
                if(lv[j]>mx)
                {
                    st=j;
                    mx=lv[j];
                }
            }
            lv[st]=1;
            dfs2(st,st);
            mx=-1;
            for(int j=1;j<=n;j++)
            {
                if(lv[j]>mx)
                {
                    mx=lv[j];
                    ed=j;
                }
            }
            break;
        }
    }
    num=ed;
    while(1)
    {
        stk.push(num);
        ++hsh[num];
        if(num==st)break;
        num=par[num];
    }
    while(!stk.empty())
    {
        line.push_back(stk.top());
        stk.pop();
    }
    memset(lv,0,sizeof lv);
    for(int i=0;i<line.size();i++)
    {
        dfs3(line[i],line[i]);

    }
    if(type==-1)
    {
        printf("NO\n");
    }else
    {

        printf("YES\n");
        printf("%d\n",2*ans.size());
        for(int i=0;i<ans.size();i++)
        {
            printf("%d ",ans[i]);
        }
        for(int i=ans.size()-1;i>=0;i--)
        {
            printf("%d ",ans[i]);
        }
        printf("\n");
    }
}

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<line.size();i++)
      |                 ~^~~~~~~~~~~~
newspapers.cpp:137:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  137 |         printf("%d\n",2*ans.size());
      |                 ~^    ~~~~~~~~~~~~
      |                  |     |
      |                  int   std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
newspapers.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for(int i=0;i<ans.size();i++)
      |                     ~^~~~~~~~~~~
newspapers.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
newspapers.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d",&u_i[i],&v_i[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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