Submission #786020

#TimeUsernameProblemLanguageResultExecution timeMemory
786020gagik_2007Newspapers (CEOI21_newspapers)C++17
100 / 100
63 ms15692 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=300007; ll n,m,k; vector<ll>g[N]; ll sz[N]; bool used[N]; ll head[N]; void dfs(int v, int par=-1){ // cout<<"YOO"<<endl; sz[v]=0; for(int to:g[v]){ if(to!=par){ dfs(to,v); sz[v]=max(sz[v],sz[to]+1); } } } bool is_tree(int c, int v, int par=-1){ used[v]=true; head[v]=c; bool retval=true; for(int to:g[v]){ if(to!=par){ if(used[to])retval= false; else if(!is_tree(c,to,v))retval= false; } } return retval; } void construct(vector<int>& p, int v, int par=-1){ // cout<<"CONSTRUCT: "<<v<<" "<<par<<endl; dfs(v); // cout<<"SZ: "; // for(int vv=1;vv<=n;vv++)cout<<sz[vv]<<" "; // cout<<endl; p.push_back(v); int u=-1; for(int to:g[v]){ if(to!=par){ if(sz[to]==1){ p.push_back(to); p.push_back(v); } else if(sz[to]!=0) u=to; } } if(u!=-1)construct(p,u,v); } int find_leaf(int v, int par=-1){ dfs(v); for(int to:g[v]){ if(to!=par){ if(sz[to]>=2){ return find_leaf(to,v); } } } for(int to:g[v]){ if(sz[to]==1)return to; } return v; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("output.txt","w",stdout); // freopen("input.txt","r",stdin); cin>>n>>m; // if(m!=n-1)cout<<"NO\n"; for(int i=0;i<m;i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } if(n==1&&m==0){ cout<<"YES 1 1\n"; return 0; } for(int v=1;v<=n;v++){ if(!used[v]&&!is_tree(v,v)){ cout<<"NO\n"; return 0; } } for(int v=1;v<=n;v++){ dfs(v); int cnt=0; for(int to:g[v]){ cnt+=(sz[to]>=2); } if(cnt>2){ cout<<"NO\n"; return 0; } } cout<<"YES\n"; vector<int>p; int leaf=find_leaf(1); // cout<<"leaf: "<<leaf<<endl; construct(p,leaf); if(p.size()>=3&&p[p.size()-1]==p[p.size()-3])p.pop_back(); int len=p.size(); for(int i=len-1;i>=0;i--){ p.push_back(p[i]); } cout<<p.size()<<endl; for(int x:p)cout<<x<<" "; cout<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...