oj.uz

Submission #552948

# Submission time Handle Problem Language Result Execution time Memory
552948 2022-04-24T10:55:09 Z ToroTN Newspapers (CEOI21_newspapers) C++14
8 / 100
 1 ms 468 KB 
#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];
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)
        {
            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();
    }
    for(int i=0;i<line.size();i++)
    {
        dfs3(line[i],line[i]);
    }
    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

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

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -