Submission #83917

#TimeUsernameProblemLanguageResultExecution timeMemory
83917facelessPotemkin cycle (CEOI15_indcyc)C++17
30 / 100
187 ms7132 KiB
#include <bits/stdc++.h> #define MP make_pair #define F first #define PB push_back #define S second using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; const int maxn = 1e3 + 4; vector <int> adj[maxn]; int mat[maxn][maxn]; int par[maxn]; bool mark[maxn]; void find_path (int v, int u, int w) { queue <int> q; memset (par, -1, sizeof par); q.push (v); par[v] = 0; while (!q.empty()) { int x = q.front(); q.pop(); for (auto y : adj[x]) { if (par[y] == -1 and y != u and (!mark[y] or y == w)) { par[y] = x; q.push(y); } } } while (w != 0) { cout << w << " "; w = par[w]; } cout << u << endl; exit(0); } int get(int v) { if (par[v] == -1) return v; return par[v] = get(par[v]); } void merge(int v, int u) { v = get(v), u = get(u); if (v == u) return; par[v] = u; } pii e[100005]; int main (){ ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int v, u; cin >> v >> u; e[i] = {v, u}; adj[v].PB(u); adj[u].PB(v); mat[v][u] = 1; mat[u][v] = 1; } for (int i = 1; i <= n; i++) { memset (par, -1, sizeof par); for (auto v : adj[i]) { mark[v] = 1; } for (int j = 0; j < m; j++) { if (e[j].F != i and e[j].S != i and (!mark[e[j].F] or !mark[e[j].S])) { merge (e[j].F, e[j].S); } } for (int j = 0; j < adj[i].size(); j++) { for (int k = j + 1; k < adj[i].size(); k++) { int v = adj[i][j], u = adj[i][k]; if (!mat[v][u] and get(v) == get(u)) find_path (v, i, u); } } for (auto v : adj[i]) { mark[v] = 0; } } cout << "no" << endl; }

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < adj[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
indcyc.cpp:79:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = j + 1; k < adj[i].size(); k++) {
                        ~~^~~~~~~~~~~~~~~
#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...