Submission #1148115

#TimeUsernameProblemLanguageResultExecution timeMemory
1148115iahParachute rings (IOI12_rings)C++20
37 / 100
639 ms105000 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair < int , int > #define fi first #define se second #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++) #define bit(x, i) (((x) >> (i)) & 1ll) #define mask(x) (1ll << (x)) #define mem(f, x) memset(f, x, sizeof(f)) #define sz(x) (int32_t) (x.size()) const int nmax = 1e6; int n, st = 0, en = 0, par[nmax + 7]; bool ok[nmax + 7], vis[nmax + 7], four, found_cycle = 0, fc; vector < int > ans, adj[nmax + 7]; struct DSU { int sz[nmax + 7], par[nmax + 7]; void init(int n) { iota(par, par + n, 0); REP(i, n) { sz[i] = 1; } } int find_par(int i) { return (par[i] == i ? i : par[i] = find_par(par[i])); } bool unite(int u, int v) { u = find_par(u); v = find_par(v); if (u == v) { return 0; } if (sz[u] < sz[v]) { swap(u, v); } par[v] = u; sz[u] += sz[v]; return 1; } }dsu; void Init(int N_) { n = N_; ans.resize(n); iota(ans.begin(), ans.end(), 0); REP(i, n) { adj[i].push_back(i); } dsu.init(n); } void dfs(int i, int j) { // cout << "dfs " << j << " " << i << "\n"; vis[i] = 1; for (auto x: adj[i]) { if (en || st) { break; } // cout << "edge " << i << " " << x << "\n"; if (x == j || x == i) { continue; } if (vis[x]) { en = i; st = x; break; } par[x] = i; dfs(x, i); } } vector < int > find_cycle() { REP(i, n) { if (!vis[i]) { dfs(i, -1); } } // REP(i, n) { // cout << vis[i] << " " << par[i] << "\n"; // } // cout << st << " " << en << "\n"; vector < int > cycle; while (en != st) { // cerr << en << "\n"; cycle.push_back(en); en = par[en]; } cycle.push_back(en); return move(cycle); } void add(vector < int > &vec) { // cout << "add "; // for (auto x: vec) { // cout << x << " "; // } // cout << "\n"; for (auto x: vec) { ok[x] = 1; } for (auto &x: ans) { if (!ok[x]) { x = -1; } } sort(ans.begin(), ans.end(), greater < int > ()); while (!ans.empty() && ans.back() == -1) { ans.pop_back(); } for (auto x: vec) { ok[x] = 0; } } void Link(int A, int B) { if (ans.empty()) { return; } adj[A].push_back(B); adj[B].push_back(A); if (!dsu.unite(A, B)) { if (!found_cycle) { found_cycle = 1; vector < int > cycle = find_cycle(); add(cycle); } else { if (dsu.find_par(ans[0]) != dsu.find_par(A)) { vector < int > ().swap(ans); return; } fc = 1; for (auto &x: ans) { if (sz(adj[x]) < 4) { x = -1; } } sort(ans.begin(), ans.end(), greater < int > ()); while (!ans.empty() && ans.back() == -1) { ans.pop_back(); } } } for (auto x: {A, B}) { if (sz(adj[x]) == 5) { if (four) { vector < int > ().swap(ans); return; } else { four = 1; bool ok = 0; for (auto i: ans) { if (i == x) { ok = 1; } } vector < int > ().swap(ans); if (ok) { ans.push_back(x); } } } if (sz(adj[x]) == 4) { add(adj[x]); } } // cout << "link " << A << " " << B << "\n"; // for (auto x: ans) { // cout << x << " "; // } // cout << "\n"; } int CountCritical() { // for (auto x: ans) { // cout << x << " "; // } // cout << "\n"; return sz(ans); }
#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...