제출 #1069312

#제출 시각아이디문제언어결과실행 시간메모리
1069312vjudge1Potemkin cycle (CEOI15_indcyc)C++17
40 / 100
197 ms18972 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back const int N = 1005; const int mod = 1e6 + 7; const int oo = 2e9; const int M = 100050; typedef long long ll; typedef pair<int,int> pii; vector <int> g[N]; int ng[N][N]; int sz[N]; int cnt; int visi[N]; pii edges[M]; int curr[N]; int main() { #ifdef LOCAL freopen("input.txt","r",stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector <vector<int>> dir(n, vector<int>(n, 0)); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; u--;v--; dir[u][v] = dir[v][u] = 1; g[u].pb(v); g[v].pb(u); edges[i] = {u, v}; } for (int j = 0; j < n; ++j) { vector <int> npss(n, 0); npss[j] = 1; for (auto &v : g[j]) npss[v] = 1; for (int i = 0; i < n; ++i) sz[i] = 0, visi[i] = 0; for (int dume = 0; dume < m; ++dume) { auto &e = edges[dume]; if (npss[e.ff] || npss[e.ss]) continue; ng[e.ff][sz[e.ff]++] = e.ss; ng[e.ss][sz[e.ss]++] = e.ff; } cnt = 1; for (int i = 0; i < n; ++i) { if (npss[i] == 0 && !visi[i]) { int curr_siz = 0; curr[curr_siz++] = i; visi[i] = cnt; while (curr_siz > 0) { int u = curr[curr_siz--]; for (int i = 0; i < sz[u]; ++i) { int v = ng[u][i]; if (!visi[v] && npss[v] == 0) visi[v] = cnt, curr[curr_siz++] = v; } } cnt++; } } vector <vector<int>> incomp(n); for (auto &v : g[j]) { for (auto &v2 : g[v]) { if (npss[v2] == 0) { for (auto &h : incomp[visi[v2]]) { if (!dir[h][v]) { pii e = {v, j}; vector <int> npss2 (n, 0); vector <int> di (n, oo); vector <int> fat (n, -1); npss2[e.ss] = 1; for (auto &v : g[e.ss]) { npss2[v] = 1; } queue <int> q; q.push(e.ff); di[e.ff] = 0; while (q.size()) { int u = q.front(); q.pop(); for (auto &v : g[u]) { if (di[v] == oo) { di[v] = di[u] + 1; fat[v] = u; if (npss2[v] == 0) q.push(v); } } } //cout << e.ff << " " << e.ss << "\n"; for (int i = 0; i < n; ++i) { //cout << i << " " << npss[i] << " " << di[i] << '\n'; if (i != e.ff && npss2[i] && di[i] < oo && di[i] > 1) { cout << e.ss + 1 << " "; int cur = i; while (cur != -1) { cout << cur + 1 << " "; cur = fat[cur]; } cout << '\n'; return 0; } } assert(h != e.ff && npss2[h] && di[h] < oo && di[h] > 1); } } } } for (auto &v2 : g[v]) { if (npss[v2] == 0) { incomp[visi[v2]].pb(v); } } } } 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...