Submission #1097510

#TimeUsernameProblemLanguageResultExecution timeMemory
1097510alexander707070Newspapers (CEOI21_newspapers)C++14
54 / 100
153 ms18516 KiB
#include<bits/stdc++.h> #define MAXN 600007 using namespace std; int n,m,a,b,ver,cnt; vector<int> v[MAXN]; vector<int> path; bool dfs(int x,int p,int dep){ if(dep==1)return true; for(int i:v[x]){ if(i==p)continue; if(dfs(i,x,dep-1))return true; } return false; } void dfs2(int x,int p){ if(cnt<ver)path.push_back(x); cnt++; for(int i:v[x]){ if(i==p or v[i].size()==1)continue; dfs2(i,x); if(cnt<ver)path.push_back(x); } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } if(m>n-1){ cout<<"NO\n"; return 0; } for(int i=1;i<=n;i++){ if(v[i].size()<=2)continue; int br=0; for(int f:v[i]){ if(dfs(f,i,3))br++; } if(br>2){ cout<<"NO\n"; return 0; } } cout<<"YES\n"; if(n==1)cout<<"1\n1\n"; else if(n==2)cout<<"2\n1 1\n"; else{ for(int i=1;i<=n;i++){ if(v[i].size()>1)ver++; } for(int i=1;i<=n;i++){ if(v[i].size()==1)continue; dfs2(i,0); cout<<path.size()*2<<"\n"; for(int f:path)cout<<f<<" "; if(path.size()%2==0)reverse(path.begin(),path.end()); for(int f:path)cout<<f<<" "; cout<<"\n"; return 0; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...