Submission #1258123

#TimeUsernameProblemLanguageResultExecution timeMemory
1258123anha3k25cvpPotemkin cycle (CEOI15_indcyc)C++20
70 / 100
1096 ms5512 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 5 + 1e5; const int inf = 7 + 1e9; struct Edge { int u, v; }; int main() { #define TASKNAME "" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen (TASKNAME".inp", "r", stdin); freopen (TASKNAME".out", "w", stdout); } int n, m; cin >> n >> m; vector <vector <int>> adj(n + 1), connected(n + 1, vector <int> (n + 1, 0)); vector <Edge> e(m + 1); for (int i = 1; i <= m; i ++) { cin >> e[i].u >> e[i].v; connected[e[i].u][e[i].v] = connected[e[i].v][e[i].u] = 1; adj[e[i].u].push_back(i); adj[e[i].v].push_back(i); } for (int edge = 1; edge <= m; edge ++) { vector <int> a(n + 1, 1), b(m + 1, 1); b[edge] = 0; for (int w = 1; w <= n; w ++) if (connected[e[edge].u][w] && connected[e[edge].v][w]) a[w] = 0; vector <int> dp(n + 1, -1), tr(n + 1, 0); queue <int> q; q.push(e[edge].u); dp[e[edge].u] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int id : adj[u]) { int v = e[id].u + e[id].v - u; if (!a[v] || !b[id]) continue; if (dp[v] == -1) { dp[v] = dp[u] + 1; tr[v] = u; q.push(v); } } } if (dp[e[edge].v] > 0) { int v = e[edge].v; cout << v << ' '; while (v != e[edge].u) { cout << tr[v] << ' '; v = tr[v]; } return 0; } } cout << "no"; return 0; } // #include <bits/stdc++.h> // #define ll long long // #define ull unsigned long long // #define dl double // #define st first // #define nd second // #define II pair <int, int> // using namespace std; // const int N = 1 + 1e3; // const int inf = 7 + 1e9; // struct Edge { // int u, v; // }; // int s = -1, t = -1; // vector <Edge> e; // vector <int> deg, vis, p; // vector <vector <int>> adj; // void dfs(int u) { // if (s >= 0) // return; // vis[u] = 1; // for (int v : adj[u]) { // if (!vis[v]) { // p[v] = u; // // cout << "- " << u << ' ' << v << '\n'; // dfs(v); // } // else if (s < 0 && vis[v] == 1) { // s = u; // t = v; // } // if (s >= 0) // return; // } // vis[u] = 2; // } // int main() { // #define TASKNAME "" // ios_base :: sync_with_stdio (0); // cin.tie (0); // if ( fopen( TASKNAME".inp", "r" ) ) { // freopen (TASKNAME".inp", "r", stdin); // freopen (TASKNAME".out", "w", stdout); // } // int n, m; // cin >> n >> m; // e.resize(2 * m + 2); // vector <vector <int>> f(n + 1, vector <int> (n + 1, 0)); // for (int i = 1; i <= m; i ++) { // cin >> e[i].u >> e[i].v; // f[e[i].u][e[i].v] = i * 2; // f[e[i].v][e[i].u] = i * 2 + 1; // } // adj.resize(2 * m + 2); // for (int i = 1; i <= m; i ++) { // int u = e[i].u, v = e[i].v; // for (int w = 1; w <= n; w ++) // if (w != u && w != v) { // if (f[v][w] && !f[u][w]) // adj[i * 2].push_back(f[v][w]); // if (f[u][w] && !f[v][w]) // adj[i * 2 + 1].push_back(f[u][w]); // } // } // for (int i = m; i > 0; i --) { // e[i * 2] = e[i]; // e[i * 2 + 1] = {e[i].v, e[i].u}; // } // vis.assign(2 * m + 2, 0); // p.assign(2 * m + 2, 0); // for (int i = 2; i < m * 2 + 2; i ++) // if (!vis[i]) { // p[i] = 0; // dfs(i); // if (s >= 0) // break; // } // if (s < 0) { // cout << "no"; // return 0; // } // vector <int> c; // c.push_back(e[s].u); // while (s != t) { // s = p[s]; // c.push_back(e[s].u); // } // for (int i = (int)c.size() - 1; i >= 0; i --) // for (int j = i + 3; j < c.size(); j ++) // if (f[c[i]][c[j]]) { // for (int u = i; u <= j; u ++) // cout << c[u] << ' '; // return 0; // } // return 0; // }

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:23:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:24:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...