Submission #1069257

#TimeUsernameProblemLanguageResultExecution timeMemory
1069257vjudge1Potemkin cycle (CEOI15_indcyc)C++17
80 / 100
1095 ms2948 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back const int N = 1005; const int mod = 1e6 + 7; const int oo = 2e9; typedef long long ll; typedef pair<int,int> pii; vector <int> g[N]; int main() { #ifdef LOCAL freopen("input.txt","r",stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector <pii> edges; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; u--;v--; g[u].pb(v); g[v].pb(u); edges.pb({u, v}); } for (auto &e : edges) { vector <int> npss (n, 0); vector <int> di (n, oo); vector <int> fat (n, -1); npss[e.ss] = 1; for (auto &v : g[e.ss]) { npss[v] = 1; } queue <int> q; q.push(e.ff); di[e.ff] = 0; while (q.size()) { int u = q.front(); q.pop(); for (auto &v : g[u]) { if (di[v] == oo) { di[v] = di[u] + 1; fat[v] = u; if (npss[v] == 0) q.push(v); } } } //cout << e.ff << " " << e.ss << "\n"; for (int i = 0; i < n; ++i) { //cout << i << " " << npss[i] << " " << di[i] << '\n'; if (i != e.ff && npss[i] && di[i] < oo && di[i] > 1) { cout << e.ss + 1 << " "; int cur = i; while (cur != -1) { cout << cur + 1 << " "; cur = fat[cur]; } cout << '\n'; return 0; } } } 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...