Submission #1258959

#TimeUsernameProblemLanguageResultExecution timeMemory
1258959nqknhtPotemkin cycle (CEOI15_indcyc)C++20
40 / 100
9 ms2140 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define len(s) (ll) s.size() #define LS(x) (1 << x) const ll I = 3e5 + 9; const ll Z = 1e9 + 7; using namespace std; int u[I], v[I], n, m; vector<int> adj[1506]; namespace sub1 { int dis[156], trace[145]; bool markE[141][156], off[156], check[145]; queue<int> q; void solve() { for (int i = 1; i <= m; i++) markE[u[i]][v[i]] = markE[v[i]][u[i]] = true; for (int i = 1; i <= m; i++) { memset(off, false, sizeof off); for (int j = 1; j <= n; j++) if (markE[j][u[i]] && markE[j][v[i]]) off[j] = true; memset(check, false, sizeof check); dis[u[i]] = 0; check[u[i]] = true; q.push(u[i]); while (!q.empty()) { int af = q.front(); q.pop(); for (auto z : adj[af]) { if (off[z] || check[z] || (z == v[i] && af == u[i])) continue; dis[z] = dis[af] + 1; trace[z] = af; check[z] = true; q.push(z); } } if (dis[v[i]] >= 3 && dis[v[i]] < n) { cout << v[i] << " "; int cur = v[i]; while (cur != u[i]) { cur = trace[cur]; cout << cur << " "; } return; } } cout << "no"; } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u[i] >> v[i]; adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); } if(n <= 100 && m <= 20000) sub1::solve(); 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...