Submission #958667

#TimeUsernameProblemLanguageResultExecution timeMemory
958667GhettoPotemkin cycle (CEOI15_indcyc)C++17
20 / 100
36 ms3156 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int MAX_N = 1e3 + 5; int n, r; vector<int> adj[MAX_N]; int depth[MAX_N]; int par[MAX_N]; unordered_set<int> children[MAX_N]; vector<pii> back_adj[MAX_N]; // {depth, node} bool seen[MAX_N]; void dfs1(int u, int d) { seen[u] = true; depth[u] = d; for (int v : adj[u]) { if (seen[v]) continue; par[v] = u; children[u].insert(v); dfs1(v, d + 1); } } void precomp() { for (int i = 1; i <= n; i++) { if (seen[i]) continue; dfs1(i, 0); } for (int i = 1; i <= n; i++) { for (int j : adj[i]) { if (depth[j] > depth[i] - 2) continue; // No double edge between child and par back_adj[i].push_back({depth[j], j}); } sort(back_adj[i].rbegin(), back_adj[i].rend()); } } void dfs2(int u, int max_depth) { for (pii el : back_adj[u]) { int v = el.second; assert(depth[v] < depth[u]); if (depth[u] - depth[v] < 3 || max_depth >= depth[v]) max_depth = max(max_depth, depth[v]); else { int w = u; while (true) { cout << w << " "; if (w == v) break; w = par[w]; } exit(0); } } for (int v : children[u]) dfs2(v, max_depth); } int main() { // freopen("cycle.in", "r", stdin); cin >> n >> r; for (int i = 1; i <= r; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } precomp(); // for (int i = 1; i <= n; i++) { // cout << i << ": "; // for (int j : children[i]) cout << j << " "; // cout << endl; // } for (int i = 1; i <= n; i++) { if (par[i]) continue; dfs2(i, -1); } 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...