Submission #1259607

#TimeUsernameProblemLanguageResultExecution timeMemory
1259607nqknhtPotemkin cycle (CEOI15_indcyc)C++20
50 / 100
1101 ms121460 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 subfull { int gen(int u, int v) { // if(u > v) swap(u, v); // cout << (u - 1) * n + v << "\n"; return (u - 1) * n + v; } pair<int, int> decode(int x) { int u = x / n; int v = x % n; if (v == 0) v = n; else u++; return make_pair(u, v); } int id[1009][1009]; int icycle = 0, vis[2000009]; vector<ll> G[1000009]; vector<vector<int>> adj; void dfs(int x) { if (icycle) return; vis[x] = 1; for (auto z : adj[x]) { if (vis[z] == 1) { icycle = z; return; } dfs(z); if (icycle == -1) return; if (icycle != 0) { int p = z / 2; if (z % 2 == 1) cout << v[p] << " "; else cout << u[p] << " "; if (z == icycle) icycle = -1; return; } } vis[x] = 2; } void solve() { for (int i = 1; i <= m; i++) { id[u[i]][v[i]] = i * 2; id[v[i]][u[i]] = i * 2 + 1; } adj.resize(m * 2 + 2); for (int i = 1; i <= m; i++) { for (int w = 1; w <= n; w++) { if (id[v[i]][w] && !id[u[i]][w] && u[i] != w) adj[i * 2].push_back(id[v[i]][w]); if (id[u[i]][w] && !id[v[i]][w] && v[i] != w) adj[i * 2 + 1].push_back(id[u[i]][w]); } } memset(vis, 0, sizeof vis); for (int i = 1; i <= m * 2 + 1; i++) { if (vis[i] == 0) dfs(i); if (icycle > 0) if (i % 2 == 1) cout << v[i / 2]; else cout << u[i / 2]; if (icycle != 0) 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]; subfull::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...