Submission #223740

#TimeUsernameProblemLanguageResultExecution timeMemory
223740staniewzkiParachute rings (IOI12_rings)C++17
100 / 100
921 ms60888 KiB
#include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < n; i++) template<class T> int size(T && a) { return (int) a.size(); } struct Graph { vector<int> rep, deg; int excluded = -1; int find(int x) { return rep[x] < 0 ? x : find(rep[x]); } int bicomp = -1; int get_cycle() { return -rep[find(bicomp)]; } void join(int x, int y) { x = find(x), y = find(y); if(x == y) { if(bicomp == -1) bicomp = x; else bicomp = -2; return; } if(rep[x] > rep[y]) swap(x, y); rep[x] += rep[y]; rep[y] = x; } int max_deg = 0; void add_edge(int a, int b) { if(a == excluded || b == excluded) return; max_deg |= 3 <= ++deg[a]; max_deg |= 3 <= ++deg[b]; join(a, b); } Graph(int n = 0, int e = -1) : rep(n, -1), deg(n), excluded(e) {} }; int n; vector<pair<int, int>> edges; Graph graph; vector<Graph> without; void Init(int N) { n = N; graph = Graph(n); } void Link(int A, int B) { edges.emplace_back(A, B); if(!graph.max_deg) { graph.add_edge(A, B); if(graph.max_deg) { if(graph.deg[A] != 3) swap(A, B); vector<int> crit = {A}; for(auto &[u, v] : edges) { if(u == A) crit.emplace_back(v); if(v == A) crit.emplace_back(u); } for(int x : crit) { without.emplace_back(n, x); for(auto &[u, v] : edges) without.back().add_edge(v, u); } } } else { for(auto &g : without) g.add_edge(A, B); } } int CountCritical() { if(!graph.max_deg) { if(graph.bicomp == -1) return n; if(graph.bicomp == -2) return 0; return graph.get_cycle(); } else { int ret = 0; for(auto &g : without) { if(g.bicomp == -1 && !g.max_deg) ret++; } return ret; } }
#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...