제출 #828170

#제출 시각아이디문제언어결과실행 시간메모리
828170jlallas384낙하산 고리들 (IOI12_rings)C++17
20 / 100
1654 ms262144 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 CountCritical(){ if(bad) return 0; else return ans.size(); } 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; map<int, ufds> mp; void Link(int a, int b){ if(bad || ans.size() == 0) return; 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); if(mp.size()){ set<int> nans; for(int x: ans) if(x != a && x != b){ int bad = 0; if(!mp[x].unite(a, b)){ bad = 1; } if(!bad) nans.insert(x); } ans = nans; assert(ans.size() <= 2); } if(!res){ if(!cyc){ dfs(a, -1, b); ans = {}; for(int x: path){ ans.insert(x); } cyc = 1; }else{ if(mp.size() == 0){ set<int> nans; for(int x: ans){ mp[x] = ufds(n); int tbad = 0; for(auto [u, v]: eds){ if(u != x && v != x){ if(!mp[x].unite(u, v)) tbad = 1; } } if(!tbad) nans.insert(x); } ans = nans; assert(ans.size() <= 2); } } }else{ tree[a].push_back(b); tree[b].push_back(a); } }
#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...