Submission #1189130

#TimeUsernameProblemLanguageResultExecution timeMemory
1189130julia_08Parachute rings (IOI12_rings)C++20
37 / 100
861 ms327680 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10; int pai[MAXN][5], sz[MAXN][5]; int id[MAXN]; int deg[MAXN][5]; set<int> comp_ciclos; vector<int> cand_critical; vector<int> adj[MAXN]; vector<pair<int, int>> links; bool first_update; int deg_3, deg_4; int get(int v, int x){ if(v == pai[v][x]) return v; return pai[v][x] = get(pai[v][x], x); } void dsu_union(int a, int b, int x){ a = get(a, x); b = get(b, x); if(sz[a][x] > sz[b][x]) swap(a, b); pai[a][x] = b; sz[b][x] += sz[a][x]; } int n; void Init(int n_){ n = n_; comp_ciclos.clear(); cand_critical.clear(); deg_3 = deg_4 = 0; first_update = true; for(int i=1; i<=n; i++) id[i] = -1; for(int i=1; i<=n; i++){ for(int j=0; j<5; j++){ sz[i][j] = 1; pai[i][j] = i; deg[i][j] = 0; } } } void dsu_init(int v){ for(auto [a, b] : links){ if(a == v || b == v) continue; if(get(a, id[v]) == get(b, id[v])){ id[v] = -1; } else{ dsu_union(a, b, id[v]); if(deg[a][id[v]] > 1 || deg[b][id[v]] > 1) id[v] = -1; } deg[a][id[v]] ++; deg[b][id[v]] ++; } } void Link(int a, int b){ a ++; b ++; links.push_back({a, b}); adj[a].push_back(b); adj[b].push_back(a); for(auto v : cand_critical){ if(id[v] == -1) continue; if(a == v || b == v) continue; if(get(a, id[v]) == get(b, id[v])){ id[v] = -1; } else{ dsu_union(a, b, id[v]); if(deg[a][id[v]] > 1 || deg[b][id[v]] > 1) id[v] = -1; } deg[a][id[v]] ++; deg[b][id[v]] ++; } if(get(a, 0) == get(b, 0)){ comp_ciclos.insert(get(a, 0)); } else dsu_union(a, b, 0); deg[a][0] ++; deg[b][0] ++; if(deg[a][0] == 3) deg_3 ++; if(deg[a][0] == 4) deg_4 ++; if(deg[b][0] == 3) deg_3 ++; if(deg[b][0] == 4) deg_4 ++; vector<int> new_cand_critical; bool update_cand_critical = false; if(deg_4 == 1 && (deg[a][0] >= 4 || deg[b][0] >= 4)){ update_cand_critical = true; if(deg[a][0] >= 4) new_cand_critical = {a}; if(deg[b][0] >= 4) new_cand_critical = {b}; } else if(deg[a][0] == 3 && deg[b][0] == 3){ update_cand_critical = true; vector<int> cand_a = {a, adj[a][0], adj[a][1], adj[a][2]}; vector<int> cand_b = {b, adj[b][0], adj[b][1], adj[b][2]}; for(auto v : cand_a){ bool ok = false; for(auto u : cand_b) ok |= (u == v); if(ok) new_cand_critical.push_back(v); } } else if(deg[a][0] == 3 || deg[b][0] == 3){ if(deg[a][0] != 3) swap(a, b); update_cand_critical = true; new_cand_critical = {a, adj[a][0], adj[a][1], adj[a][2]}; } if(update_cand_critical){ if(first_update){ for(auto v : new_cand_critical){ cand_critical.push_back(v); id[v] = cand_critical.size(); dsu_init(v); } first_update = false; } else{ for(auto v : cand_critical){ bool ok = false; for(auto u : new_cand_critical) ok |= (u == v); if(!ok) id[v] = -1; } } } } int CountCritical(){ if(deg_4 > 1) return 0; if(deg_3 == 0){ if(comp_ciclos.size() > 1) return 0; if(comp_ciclos.size() == 1) return sz[get(*comp_ciclos.begin(), 0)][0]; return n; } int ans = 0; for(auto v : cand_critical) if(id[v] != -1) ans ++; return 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...