| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 223742 | staniewzki | 낙하산 고리들 (IOI12_rings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
clude<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 = max(max_deg, ++deg[a]);
max_deg = max(max_deg, ++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 < 3) {
graph.add_edge(A, B);
if(graph.max_deg == 3) {
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 < 3) {
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 < 3)
ret++;
}
return ret;
}
}