Submission #1166274

#TimeUsernameProblemLanguageResultExecution timeMemory
1166274ByeWorldNewspapers (CEOI21_newspapers)C++20
50 / 100
127 ms15880 KiB
#include <bits/stdc++.h> #define int long long #define ll long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<char,char> pcc; typedef pair<pii,int> ipii; typedef pair<pii,pii> ipiii; const int MAXN = 3e5+10; const int SQRT = 300; const int MAXA = 50; const int LOG = 20; const int INF = 1e18+10; const ld EPS = 1e-6; const int MOD = 998244353; int sum(int a, int b){ return (a+b)%MOD; } void chsum(int &a, int b){ a = (a+b)%MOD; } void chsub(int &a, int b){ a = (a+MOD-b)%MOD; } int mul(int a, int b){ return (a*b)%MOD; } void chmul(int &a, int b){ a = (a*b)%MOD; } void chmn(int &a, int b){ a = min(a, b); } void chmx(int &a, int b){ a = max(a, b); } int n, m; vector <int> adj[MAXN]; int mx=0; void dfs(int nw, int par, int dis){ chmx(mx, dis); for(auto nx : adj[nw]){ if(nx==par) continue; dfs(nx,nw,dis+1); } } bool solve(){ if(m!=n-1) return 0; bool can = 1; for(int i=1; i<=n; i++){ int cnt = 0; for(auto nx : adj[i]){ mx=0; dfs(nx,i,1); if(mx>=3) cnt++; } if(cnt>=3) can = 0; } return can; } signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1; i<=m; i++){ int x, y; cin>>x>>y; adj[x].pb(y); adj[y].pb(x); } if(solve()){ cout << "YES\n1\n1\n"; } else cout << "NO\n"; } /* if(m==n-1){ int num = 0, id = -1; for(int i=1; i<=n; i++) if(adj[i].size() >= 3) num++, id = i; if(num>=2){ cout << "NO\n"; exit(0); } else if(num==1){ bool can = 1; for(int i=1; i<=n; i++){ if(i == id) continue; if(adj[i].size() >= 2) can = 0; } if(can){ cout << "YES\n2\n"; cout<<id<<' '<<id<<'\n'; } else cout << "NO\n"; exit(0); } if(n==1){ cout << "YES\n1\n1\n"; exit(0); } if(n<=3){ cout << "YES\n2\n2 2\n"; exit(0); } cout << "YES\n"; cout << 2*(n-2) << '\n'; for(int i=2; i<=n-1; i++) cout << i << ' '; for(int i=n-1; i>=2; i--) cout << i << ' '; cout << '\n'; } else { cout << "NO\n"; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...