Submission #1258617

#TimeUsernameProblemLanguageResultExecution timeMemory
1258617mquangPotemkin cycle (CEOI15_indcyc)C++20
100 / 100
386 ms118212 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; void input(){ #define taskname "" if(fopen(taskname ".inp", "r")){ freopen(taskname ".inp", "r", stdin); freopen(taskname ".out","w",stdout); } } const int N = 1e3+1; const int INF =1e9+7; ll n,m; vector<vector<ll>>g(N); vector<vector<ll>>col(N,vector<ll>(N,0)); vector<vector<pair<ll,ll>>>par(N,vector<pair<ll,ll>>(N)); void sub1(){ vector<vector<bool>>hw(n+1,vector<bool>(n+1,0)); for(ll i=0;i<m;++i){ ll u,v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); hw[u][v] = 1; hw[v][u] = 1; } bool f =0; // for(auto x : g[1]) cout << x << " "; // cout << endl; for(ll mask =0;mask < (1 << n);++mask){ if(__builtin_popcount(mask) < 4) continue; vector<ll>pth; for(ll i=1;i<=n;++i){ if((mask >> (i-1)) & 1) pth.push_back(i); } bool br = 0; ll sz = pth.size(); for(ll i=0;i<pth.size();++i){ ll j = (i + 2) % sz; while(1){ if(hw[pth[i]][pth[j]]){ br = 1; break; } if(br) break; ++j; j %= sz; if(i == 0 && j == sz-1) break; if(j == i-1) break; } if(br) break; } if(br) continue; bool ck = 0; vector<bool>vis(n+1,0); ll i=0; // for(auto x : pth) cout << x << " "; // cout << endl; while(1){ // cout << i << endl; bool ok = 0; for(auto x : g[pth[i]]){ // if(!ck) break; if(x == pth[(i+1)%sz] && !vis[x]){ ++i; vis[x] = 1; ok = 1; break; } } if(!ok) break; if(i == sz){ ck = 1; break; } } if(ck){ f = 1; for(auto x : pth) cout << x << " "; cout << '\n'; break; } } if(!f) cout << "no" << '\n'; } bool dfs(pair<ll,ll> cur,vector<vector<vector<pair<ll,ll>>>>& g){ ll u = cur.first, v = cur.second; col[u][v] = 1; for(auto x : g[u][v]){ ll u1 = x.first, v1 = x.second; if(col[u1][v1] == 0){ par[u1][v1] = {u,v}; if(dfs(x,g)) return 1; } else if(col[u1][v1] == 1) return 1; } col[u][v] = 2; return 0; } void sub4(){ vector<unordered_set<int>> adj(n+1); vector<pair<int,int>> ed; ed.reserve(m); for(int i = 0; i < m; ++i){ int u, v; cin >> u >> v; adj[u].insert(v); adj[v].insert(u); ed.push_back({u, v}); } vector<pair<int,int>> canh; for(auto &e : ed){ canh.push_back({e.first, e.second}); canh.push_back({e.second, e.first}); } int sz = canh.size(); vector<vector<int>> pos(n+1); for(int i = 0; i < sz; ++i) pos[canh[i].first].push_back(i); vector<vector<int>> g(sz); for(int i = 0; i < sz; ++i){ int u = canh[i].first; int v = canh[i].second; for(int jid : pos[v]){ int w = canh[jid].second; if(w == u) continue; if(adj[u].count(w) == 0) g[i].push_back(jid); } } vector<int> col(sz, 0), par(sz, -1); bool kt = 0; vector<int> ct; for(int s = 0; s < sz && !kt; ++s){ if(col[s] != 0) continue; vector<pair<int,int>> stk; stk.push_back({s, 0}); col[s] = 1; par[s] = -1; while(!stk.empty() && !kt){ int node = stk.back().first; int &it = stk.back().second; if(it < g[node].size()){ int to = g[node][it++]; if(col[to] == 0){ par[to] = node; col[to] = 1; stk.push_back({to, 0}); } else if(col[to] == 1){ vector<int> idxs; int cur = node; idxs.push_back(cur); while(cur != to){ cur = par[cur]; if(cur == -1) break; idxs.push_back(cur); } if(cur == -1) continue; reverse(idxs.begin(), idxs.end()); vector<int> ans; ans.push_back(canh[idxs[0]].first); for(int t = 0; t < idxs.size(); ++t) ans.push_back(canh[idxs[t]].second); if(ans.size() > 1 && ans.front() == ans.back()) ans.pop_back(); if(ans.size() >= 4){ unordered_set<int> seen; bool ok = true; for(int x : ans){ if(seen.count(x)){ ok = false; break; } seen.insert(x); } if(ok){ ct = ans; kt = true; break; } } } } else{ col[node] = 2; stk.pop_back(); } } } if(!kt){ cout << "no"; return; } for(int i = 0; i < ct.size(); ++i) cout << ct[i] << ' '; } int main(){ cin.tie(0)->sync_with_stdio(0); input(); cin >> n >> m; //if(n <= 1 && m <= 45) sub1(); //else sub4(); sub4(); return 0; } /* 4 5 1 2 2 3 3 4 4 1 1 3 */

Compilation message (stderr)

indcyc.cpp: In function 'void input()':
indcyc.cpp:10:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |                 freopen(taskname ".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:11:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |                 freopen(taskname ".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...