Submission #1190748

#TimeUsernameProblemLanguageResultExecution timeMemory
1190748PieArmyNewspapers (CEOI21_newspapers)C++20
75 / 100
42 ms4568 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; int n,m; vector<int>komsu[1023]; vector<int>ans; vector<int>anss; int par[1023],dep[1023]; void cal(int pos){ dep[pos]=0; for(int x:komsu[pos]){ if(par[pos]==x)continue; par[x]=pos; cal(x); dep[pos]=max(dep[pos],dep[x]+1); } } bool dfs(int pos){ vector<int>child; for(int x:komsu[pos]){ if(par[pos]==x)continue; child.pb(x); } sort(child.begin(),child.end(),[&](const int &x,const int &y){ return dep[x]>dep[y]; }); if(child.size()==0)return true; if(child.size()>1){ if(dep[child[1]]>1)return false; } if(dep[child[0]]==0){ ans.pb(pos); return true; } for(int x:child){ if(!dfs(x))return false; if(dep[x]==0)break; ans.pb(pos); } return true; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>m; for(int i=0;i<m;i++){ int x,y;cin>>x>>y; komsu[x].pb(y); komsu[y].pb(x); } if(m!=n-1){ cout<<"NO"<<endl; return 0; } if(n<=2){ cout<<"YES"<<endl<<n<<endl; for(int i=0;i<n;i++){ cout<<"1 "; } cout<<endl; return 0; } for(int root=1;root<=n;root++){ par[root]=0; cal(root); if(dfs(root)){ int s=ans.size(); if((dep[ans[0]]&1)!=(dep[root]&1))ans.pb(ans[0]); for(int i=0;i<s;i++){ ans.pb(ans[i]); } if(anss.size()==0||anss.size()>ans.size()){ swap(ans,anss); } } ans.clear(); } if(anss.size()){ cout<<"YES"<<endl<<anss.size()<<endl; for(int x:anss) cout<<x<<" "; cout<<endl; } else cout<<"NO"<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...