Submission #497213

#TimeUsernameProblemLanguageResultExecution timeMemory
497213VictorNewspapers (CEOI21_newspapers)C++17
52 / 100
2 ms460 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; vi graph[1001]; int n, m, cnt, start; vi ans; bool dfs(int u, int p, int dist) { //cout<<"u = "<<u+1<<" p = "<<p+1<<" dist = "<<dist<<endl; if (dist == 3) return 1; trav(v, graph[u]) if (v != p) { bool val = dfs(v, u, dist + 1); if(u==start)cnt+=val; else if(val)return 1; } return 0; } void solve(int u,int p, bool parity){ vi small, big; trav(v,graph[u])if(v!=p){ if(dfs(v,u,1))big.pb(v); else small.pb(v); } assert(sz(big)<3); if(!big.empty())solve(big[0], u, parity^1); trav(v,small){ if(sz(ans) % 2 == parity)ans.pb(u); ans.pb(v); } if(sz(ans) % 2 == parity)ans.pb(u); if(sz(big)==2)solve(big[1], u, parity^1); } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cin >> n >> m; if (m >= n) { cout << "NO" << endl; return 0; } while (m--) { int u, v; cin >> u >> v; graph[--u].pb(--v); graph[v].pb(u); } rep(i, 0, n) { cnt = 0; start=i; dfs(i, i, 0); //cout << "u = " << i + 1 << " cnt = " << cnt << endl; if (cnt >= 3) { cout << "NO" << endl; return 0; } } start = cnt = 0; dfs(0,0,0); solve(0,0,0); cout<<"YES"<<endl; cout<<sz(ans)*2+1-(sz(ans)%2)<<endl; trav(u,ans)cout<<u+1<<' '; if(sz(ans)%2==0)cout<<"1 "; trav(u,ans)cout<<u+1<<' '; cout<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...