Submission #828166

#TimeUsernameProblemLanguageResultExecution timeMemory
828166jlallas384Parachute rings (IOI12_rings)C++17
20 / 100
4086 ms152796 KiB
#include <bits/stdc++.h> using namespace std; struct ufds{ vector<int> sz, par; ufds(){} ufds(int n): sz(n, 1), par(n){ iota(par.begin(), par.end(), 0); } int find(int a){ return par[a] == a ? a : par[a] = find(par[a]); } int unite(int a, int b){ a = find(a), b = find(b); if(a == b) return 0; if(sz[a] < sz[b]) swap(a, b); par[b] = a; sz[a] += sz[b]; return 1; } }; set<int> ans; vector<vector<int>> g, tree; vector<int> deg; int n; ufds ds; int bad = 0; int d4 = 0; void Init(int N){ n = N; g.resize(n); tree.resize(n); deg.resize(n); for(int i = 0; i < n; i++){ ans.insert(i); } ds = ufds(n); } void proc(int a, int add = 1){ if(deg[a] == 4){ if(add){ d4++; if(d4 == 2) bad = 1; } if(!ans.count(a)) ans = {}; else ans = {a}; }else if(deg[a] == 3){ set<int> nans; if(ans.count(a)) nans.insert(a); for(int u: g[a]){ if(ans.count(u)) nans.insert(u); } ans = nans; } } int cyc = 0; vector<int> path; int dfs(int v, int p, int x){ path.push_back(v); if(v == x) return 1; for(int u: tree[v]) if(u != p){ if(dfs(u, v, x)) return 1; } path.pop_back(); return 0; } vector<pair<int,int>> eds; void Link(int a, int b){ int res = ds.unite(a, b); deg[a]++, deg[b]++; g[a].push_back(b); g[b].push_back(a); eds.emplace_back(a, b); proc(a), proc(b); cyc += !res; } int CountCritical(){ if(cyc == 0) return ans.size(); int fans = 0; for(int x: ans){ ufds f(n); int can = 1; for(auto [u, v]: eds) if(u != x && v != x){ if(!f.unite(u, v)) can = 0; } fans += can; } return fans; }
#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...