Submission #739054

#TimeUsernameProblemLanguageResultExecution timeMemory
739054kirakaminski968Potemkin cycle (CEOI15_indcyc)C++17
90 / 100
309 ms10076 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; bool edges[MAXN][MAXN]; int vis[MAXN][MAXN],N,parent[MAXN][MAXN]; vector<pair<int,int>> paths; void dfs(int start, int ed){ vis[start][ed] = 1; for(int i = 1;i<=N;++i){ if(i == start || vis[ed][i] == 2 || edges[start][i] || !edges[i][ed]) continue; if(vis[ed][i]){ vector<int> cycle; cycle.push_back(ed); cycle.push_back(start); while(start != i){ cycle.push_back(parent[start][ed]); int tmp = parent[start][ed]; ed = start; start = tmp; } int x = cycle.size(); int left = 0, right = x-1; for(int j = 0;j<x;++j){ for(int k = j+2;k<x;++k){ if(edges[cycle[j]][cycle[k]] && (k-j < right-left)){ left = j; right = k; } } } for(int j = left; j<right;++j) cout << cycle[j] << " "; cout << i << "\n"; exit(0); } else{ parent[ed][i] = start; dfs(ed,i); } } vis[start][ed] = 2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int R; cin >> N >> R; for(int i = 0;i<R;++i){ int a,b; cin >> a >> b; edges[a][b] = edges[b][a] = true; paths.push_back({a,b}); } for(auto e : paths){ if(!vis[e.first][e.second]){ dfs(e.first,e.second); } } cout << "no"; return 0; }
#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...