Submission #125171

#TimeUsernameProblemLanguageResultExecution timeMemory
125171eriksuenderhaufPotemkin cycle (CEOI15_indcyc)C++11
100 / 100
477 ms6296 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e3 + 5; const int MAXM = 1e5 + 5; const double eps = 1e-9; int nei[MAXN][MAXN], col[MAXN], cand[MAXN], dist[MAXN], par[MAXN]; vi adj[MAXN], tmp[MAXN]; int n, m; void dfs(int u, int root, int mx) { if (col[u]) return; col[u] = root; for (int v: adj[u]) { if (v >= mx) continue; if (cand[v]) tmp[root].pb(v); else dfs(v, root, mx); } } void dfs2(int root, int x, int y) { mem(dist, 0x3f); deque<int> pq; pq.pb(x); dist[x] = 0; par[x] = 0; while (!pq.empty()) { int u = pq.front(); pq.pop_front(); if (u == root || (cand[u] && u != x && u != y)) continue; for (int v: adj[u]) { if (dist[v] < INF || v > root) continue; par[v] = u; dist[v] = dist[u] + 1; pq.pb(v); } } printf("%d ", root); int u = y; while (u != 0) { printf("%d ", u); u = par[u]; } exit(0); } void solve(int u) { mem(cand, 0); mem(col, 0); for (int i = 1; i <= n; i++) tmp[i].clear(); for (int i = 1; i < u; i++) if (nei[u][i]) cand[i] = 1; for (int i = 1; i < u; i++) if (!cand[i] && !col[i]) dfs(i, i, u); for (int i = 1; i < u; i++) { sort(tmp[i].begin(), tmp[i].end()); tmp[i].erase(unique(tmp[i].begin(), tmp[i].end()), tmp[i].end()); for (int j = 0; j < (int)tmp[i].size(); j++) for (int k = j+1; k < (int)tmp[i].size(); k++) if (!nei[tmp[i][j]][tmp[i][k]]) dfs2(u, tmp[i][j], tmp[i][k]); } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); adj[u].pb(v); adj[v].pb(u); nei[u][v] = nei[v][u] = 1; } for (int i = n; i > 0; i--) solve(i); printf("no\n"); return 0; }

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
#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...