Submission #1115975

#TimeUsernameProblemLanguageResultExecution timeMemory
1115975vjudge1Potemkin cycle (CEOI15_indcyc)C++17
60 / 100
13 ms2384 KiB
#include <bits/stdc++.h> #define pb push_back #define spc << " " << #define endl "\n" #define all(x) x.begin(), x.end() #define int long long #define ii pair<int, int> #define vi vector<int> #define vii vector<ii> #define st first #define nd second #define mid (l+r)/2 #define inf 1e15 #define MOD 998244353 #define MX 1005 using namespace std; vi edges[MX]; bitset<MX> adj[MX]; int vis[MX]; int tim=0; int dfs(int node, int par){ vis[node]=++tim; int can=-1; for(auto i:edges[node]){ if(i==par) continue; if(vis[i]>0){ if(can==-1 || vis[i]>vis[can]) can=i; } } if(can!=-1){ cout << node+1 << " "; return can; } for(auto i:edges[node]){ if(i==par) continue; if(vis[i]!=0) continue; auto dont=adj[node]; dont&=adj[par]; if(node!=par && dont[i]==1) continue; int res=dfs(i, node); if(res==-2) return -2; if(res!=-1){ cout << node+1 << " "; if(node!=res) return res; else return -2; } } vis[node]=-1; return -1; } void solve(){ int n,m; cin >> n >> m; for(int i=0; i<n; i++){ adj[MX].reset(); vis[i]=0; } for(int i=1; i<=m; i++){ int a,b; cin >> a >> b; a--, b--; edges[a].pb(b); edges[b].pb(a); adj[a].set(b); adj[b].set(a); } if(n<4){ cout << "no" << endl; return; } if(dfs(n-1, n-1)==-1) cout << "no" << endl; } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0); #ifdef Local freopen("in","r",stdin); freopen("out","w",stdout); /*#else freopen("","r",stdin); freopen("","w",stdout);*/ #endif int t=1; //cin >> t; while(t--) solve(); }
#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...