Submission #1172801

#TimeUsernameProblemLanguageResultExecution timeMemory
1172801Dan4LifePotemkin cycle (CEOI15_indcyc)C++20
80 / 100
1093 ms1352 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) using ll = long long; using ar2 = array<ll,2>; using vi = vector<int>; const int mxN = (int)1e3+10; const ll INF = (int)1e9; const ll MOD = (ll)1e9+7; int n, m, pos[mxN]; vi adj[mxN], v; bitset<mxN> vis,skip; bitset<mxN> edge[mxN]; void dfs2(int s, vi &v){ vis[s] = 1; pos[s] = sz(v)-1; for(auto u : adj[s]){ if(vis[u]) continue; vi w; w.clear(); if(sz(adj[u])<sz(v)){ for(auto x : adj[u]){ if(pos[x]!=-1) w.pb(pos[x]); if(sz(w)==3) break; } } else{ for(int i = 0; i < sz(v); i++){ if(edge[v[i]][u]) w.pb(i); if(sz(w)==3) break; } } if(sz(w)==3) continue; if(sz(w)==2){ sort(all(w)); if(w[1]-w[0]==1) continue; for(int i = w[0]; i <= w[1]; i++) cout << v[i] << " "; cout << u << "\n"; exit(0); } v.pb(u); dfs2(u,v); v.pop_back(); pos[u]=-1; } if(n<=100) vis[s] = 0; } void dfs(int s){ vis[s] = 1; pos[s] = sz(v)-1; skip[s]=1; v.pb(s); for(auto u : adj[s]){ if(vis[u]) continue; vi w; w.clear(); if(sz(adj[u])<sz(v)){ for(auto x : adj[u]){ if(pos[x]!=-1) w.pb(pos[x]); if(sz(w)==3) break; } } else{ for(int i = 0; i < sz(v); i++){ if(edge[v[i]][u]) w.pb(i); if(sz(w)==3) break; } } if(sz(w)==3) continue; if(sz(w)==2){ sort(all(w)); if(w[1]-w[0]==1) continue; for(int i = w[0]; i <= w[1]; i++) cout << v[i] << " "; cout << u << "\n"; exit(0); } dfs(u); } vis[s] = 0; pos[s] = -1; v.pop_back(); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; edge[a][b] = edge[b][a] = 1; adj[a].pb(b), adj[b].pb(a); } memset(pos,-1,sizeof(pos)); if(n<=300){ for(int i = 1; i <= n; i++){ vis.reset(); v.pb(i); dfs2(i,v); v.pop_back(); pos[i]=-1; } cout << "no\n"; return 0; } for(int i = 1; i <= n; i++) if(!skip[i]) dfs(i); cout << "no\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...