| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 471536 | 2021-09-09T16:51:32 Z | blue | Parachute rings (IOI12_rings) | C++17 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
using namespace std;
const int maxN = 1'000'000;
struct disjoint_set
{
int S;
vector<int> parent;
vector<int> subtree;
disjoint_set()
{
;
}
disjoint_set(int s)
{
S = s;
parent = vector<int>(S);
subtree = vector<int>(S);
for(int i = 0; i < S; i++)
{
parent[i] = i;
subtree[i] = 1;
}
}
int root(int u)
{
int v = u;
while(parent[v] != v) v = parent[v];
parent[u] = v;
return v;
}
bool connected(int u, int v)
{
return root(u) == root(v);
}
void join(int u, int v)
{
u = root(u);
v = root(v);
if(u == v) return;
if(subtree[u] < subtree[v]) swap(u, v);
subtree[u] += subtree[v];
parent[v] = u;
}
};
const int X = 0;
const int Y = 1;
const int Z = 2;
//general
int state = X;
int N;
//state == X
vector<int> edge[maxN];
disjoint_set prevDSU;
int degree(int u)
{
return (int)edge[u].size();
}
//state == Y
int cyclic_count = 0;
vector<bool> cyclic(maxN, 0);
void go_to_Y(int label)
{
state = Y;
for(int i = 0; i < N; i++)
{
if(prevDSU.connected(i, label))
{
cyclic[i] = 1;
cyclic_count++;
}
}
}
//state == Z
int Zsize;
vector<int> Z_critical;
vector< vector<int> > Z_degree;
vector<disjoint_set> DSU;
vector<bool> good;
void Z_link(int A, int B)
{
for(int q = 0; q < Zsize; q++)
{
int z = Z_critical[q];
if(A == z || B == z)
{
return;
}
if(DSU[q].connected(A, B))
{
good[q] = 0;
}
Z_degree[q][A]++;
Z_degree[q][B]++;
if(Z_degree[q][A] > 2 || Z_degree[q][B] > 2)
good[q] = 0;
DSU[q].join(A, B);
}
}
void go_to_Z(vector<int> V)
{
state = Z;
Zsize = V.size();
Z_critical = V;
Z_degree = vector<int>(Zsize, 0);
DSU = vector<disjoint_set>(Zsize, disjoint_set(N));
good = vector<bool>(Zsize, 1);
for(int u = 0; u < N; u++)
{
for(int v: edge[u])
{
if(v < u) continue;
Z_link(u, v);
}
}
}
void Init(int N_)
{
N = N_;
prevDSU = disjoint_set(N);
}
void Link(int A, int B)
{
if(state == X)
{
if(!prevDSU.connected(A, B))
{
if(degree(A) <= 1 && degree(B) <= 1)
{
prevDSU.join(A, B);
edge[A].push_back(B);
edge[B].push_back(A);
}
else if(degree(A) <= 1)
{
vector<int> V = edge[B];
V.push_back(A);
V.push_back(B);
go_to_Z(V);
}
else if(degree(B) <= 1)
{
vector<int> V = edge[A];
V.push_back(A);
V.push_back(B);
go_to_Z(V);
}
else
{
go_to_Z({A, B});
}
}
else
{
if(degree(A) <= 1 && degree(B) <= 1)
{
edge[A].push_back(B);
edge[B].push_back(A);
go_to_Y(A);
}
else if(degree(A) <= 1)
{
vector<int> V = edge[B];
V.push_back(A);
V.push_back(B);
go_to_Z(V);
}
else if(degree(B) <= 1)
{
vector<int> V = edge[A];
V.push_back(A);
V.push_back(B);
go_to_Z(V);
}
else
{
go_to_Z({});
}
}
}
else if(state == Y)
{
if(cyclic[A] && cyclic[B])
{
go_to_Z({A, B});
}
else if(cyclic[A] && !cyclic[B])
{
edge[A].push_back(A);
go_to_Z(edge[A]);
}
else if(cyclic[B] && !cyclic[A])
{
edge[B].push_back(B);
go_to_Z(edge[B]);
}
else
{
if(!prevDSU.connected(A, B))
{
if(degree(A) <= 1 && degree(B) <= 1)
{
edge[A].push_back(B);
edge[B].push_back(A);
prevDSU.join(A, B);
}
else
{
go_to_Z({});
}
}
else
{
go_to_Z({});
}
}
}
else if(state == Z)
{
for(int q = 0; q < (int)Z_critical.size(); q++)
{
Z_link(A, B);
}
}
}
int CountCritical()
{
if(state == X) return N;
else if(state == Y)
{
return cyclic_count;
}
else if(state == Z)
{
int res = 0;
for(int q = 0; q < good.size(); q++)
res += good[q];
return res;
}
}