This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct disjoint_sets
{
vector<size_t> repr, rank;
disjoint_sets(size_t n) : repr(n), rank(n)
{
for(size_t i = 0; i < n; i++)
repr[i] = i;
}
size_t find(size_t v)
{
return v == repr[v] ? v : repr[v] = find(repr[v]);
}
bool unite(size_t u, size_t v)
{
if((u = find(u)) == (v = find(v)))
return false;
if(rank[u] > rank[v])
swap(u, v);
rank[v] += (rank[u] == rank[v]);
repr[u] = v;
return true;
}
};
enum BambooForestStatus
{
Ok,
Cycles,
Bad
};
struct bamboo_forest
{
BambooForestStatus status = Ok;
disjoint_sets dsets;
vector<size_t> deg;
size_t cycles = 0;
bamboo_forest(size_t n) : dsets(n), deg(n) {}
bamboo_forest() : bamboo_forest(0) {}
BambooForestStatus edge(size_t u, size_t v)
{
deg[u]++; deg[v]++;
if(deg[u] > 2 or deg[v] > 2)
status = Bad;
if((status == Ok or status == Cycles) and dsets.find(u) == dsets.find(v) and deg[u] == 2 and deg[v] == 2)
status = Cycles, cycles++;
else if(not dsets.unite(u, v))
status = Bad;
return status;
}
};
size_t n;
vector<pair<size_t, size_t>> edges;
vector<vector<size_t>> graph;
bamboo_forest base;
size_t first_cycle_size;
unordered_set<size_t> greater2, greater3;
size_t w2 = SIZE_MAX, w3 = SIZE_MAX;
bamboo_forest drop_w3;
vector<pair<size_t, bamboo_forest>> drop_w2s;
void Init(int _n)
{
n = _n;
base = bamboo_forest(n);
graph.resize(n);
}
bamboo_forest current_forest_with_drop(size_t w)
{
bamboo_forest F;
for(auto [u, v] : edges)
if(u != w and v != w)
F.edge(u, v);
return F;
}
void Link(int u, int v)
{
edges.emplace_back(u, v);
graph[u].push_back(v);
graph[v].push_back(u);
auto pre = base.status;
base.edge(u, v);
if(pre == Ok and base.status == Cycles and base.cycles == 1)
{
auto w = base.dsets.find(u);
for(size_t i = 0; i < n; i++)
if(base.dsets.find(i) == w)
first_cycle_size++;
}
if(base.deg[u] > 2) greater2.insert(u);
if(base.deg[v] > 2) greater2.insert(v);
if(base.deg[u] > 3) greater3.insert(u);
if(base.deg[v] > 3) greater3.insert(v);
if(not greater3.empty() and w3 == SIZE_MAX)
drop_w3 = current_forest_with_drop(w3 = *greater3.begin());
else if(w3 != SIZE_MAX and (size_t)u != w3 and (size_t)v != w3)
drop_w3.edge(u, v);
if(w2 == SIZE_MAX and w3 == SIZE_MAX)
{
w2 = *greater2.begin();
drop_w2s.resize(graph[w2].size() + 1, {SIZE_MAX, bamboo_forest(n)});
}
}
bool naive_try(size_t i)
{
return current_forest_with_drop(i).status == Ok;
}
int CountCritical()
{
if(base.status == Ok)
return n;
else if(base.status == Cycles and base.cycles == 1)
return first_cycle_size;
else if(base.status == Cycles and base.cycles > 1)
return 0;
else if(greater3.size() > 1)
return 0;
else
{
if(w3 != SIZE_MAX)
return drop_w3.status == Ok;
size_t result = 0, w = *greater2.begin();
for(size_t i : graph[w])
result += naive_try(i);
result += naive_try(w);
return result;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |