#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF = 1e9;
int n;
int d[MAXN];
int d2[MAXN];
struct DSU
{
int par[MAXN];
int dep[MAXN];
int sz[MAXN];
void build()
{
for (int i = 1 ; i <= n ; ++i)
{
par[i] = i;
dep[i] = 1;
sz[i] = 1;
}
}
int find(int u)
{
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
void connect(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
{
assert(false);
return;
}
if (dep[u] < dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
par[u] = v;
sz[v] += sz[u];
}
bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
DSU dsu;
DSU dsu2;
int ans;
void Init(int N_)
{
n = N_;
ans = n;
dsu.build();
}
int cycle;
bool isBad;
int cntThree;
int theNode = -1;
std::set <int> toNode;
std::set <int> toNode2;
std::vector <int> three;
std::vector <std::pair <int,int>> added;
std::vector <int> g[MAXN];
void reConnect(int node)
{
dsu.build();
theNode = node;
std::fill(d + 1, d + 1 + n, 0);
for (const auto &[u, v] : added)
{
d[u]++;
d[v]++;
if (u == node)
{
toNode.insert(v);
continue;
}
if (v == node)
{
toNode.insert(u);
continue;
}
if (dsu.areConnected(u, v))
{
isBad = true;
return;
}
dsu.connect(u, v);
}
for (int i = 1 ; i <= n ; ++i)
{
if (d[i] - toNode.count(i) > 2 && i != node)
{
isBad = true;
return;
}
}
}
bool check(int node)
{
dsu2.build();
toNode2.clear();
std::fill(d2 + 1, d2 + 1 + n, 0);
for (const auto &[u, v] : added)
{
d2[u]++;
d2[v]++;
if (u == node)
{
toNode2.insert(v);
continue;
}
if (v == node)
{
toNode2.insert(u);
continue;
}
if (dsu2.areConnected(u, v))
{
return false;
}
dsu2.connect(u, v);
}
for (int i = 1 ; i <= n ; ++i)
{
if (d2[i] - toNode2.count(i) > 2 && i != node)
{
return false;
}
}
return true;
}
bool isLenThree = false;
void Link(int u, int v)
{
u++;
v++;
if (isBad)
{
return;
}
added.push_back({u, v});
if (theNode != -1)
{
if (v == theNode)
{
std::swap(u, v);
}
if (u == theNode)
{
d[v]++;
toNode.insert(v);
if (d[v] > 3)
{
isBad = true;
return;
}
} else
{
d[v]++;
d[u]++;
if (d[v] - toNode.count(v) > 2)
{
isBad = true;
return;
}
if (d[u] - toNode.count(u) > 2)
{
isBad = true;
return;
}
if (dsu.areConnected(u, v))
{
isBad = true;
return;
}
dsu.connect(u, v);
}
} else
{
d[u]++;
d[v]++;
if (d[u] == 4 && d[v] == 4)
{
isBad = true;
return;
}
if (d[u] == 4)
{
reConnect(u);
return;
}
if (d[v] == 4)
{
reConnect(v);
return;
}
cntThree += (d[u] == 3);
cntThree += (d[v] == 3);
g[u].push_back(v);
g[v].push_back(u);
if (d[u] == 3)
{
three.push_back(u);
}
if (d[v] == 3)
{
three.push_back(v);
}
if (cycle && dsu.areConnected(u, v))
{
isLenThree = false;
if (dsu.find(u) != dsu.find(cycle))
{
isBad = true;
return;
}
assert(cntThree > 1);
if (!check(three[0]))
{
isBad = true;
return;
}
}
if (!cycle && dsu.areConnected(u, v))
{
for (const int &x : g[u])
{
if (x == v)
{
isLenThree = true;
}
}
cycle = u;
}
if (!dsu.areConnected(u, v))
{
dsu.connect(u, v);
}
if (cycle)
{
if (isLenThree)
{
ans = 3;
return;
}
if (cntThree > 2)
{
isBad = true;
return;
}
for (const int &u : three)
{
if (dsu.find(u) != dsu.find(cycle))
{
isBad = true;
return;
}
}
if (cntThree == 2)
{
bool good = false;
for (const int &i : g[three[0]])
{
if (i == three[1])
{
good = true;
}
}
if (!good)
{
isBad = true;
return;
}
}
if (cntThree == 0)
{
ans = dsu.sz[dsu.find(cycle)];
return;
}
if (cntThree == 1)
{
ans = 3;
return;
}
ans = 2;
return;
}
if (cntThree > 4)
{
isBad = true;
return;
}
if (cntThree == 0)
{
ans = n;
return;
}
if (cntThree == 1)
{
ans = 4;
return;
}
ans = 0;
for (const int &i : three)
{
int curr = 0;
for (const int &u : g[i])
{
curr += (d[u] == 3);
}
if (curr == cntThree - 1)
{
ans++;
}
}
if (cntThree == 2)
{
for (const int &u : g[three[0]])
{
for (const int &v : g[three[1]])
{
if (u == v)
{
ans++;
}
}
}
}
}
}
int CountCritical()
{
if (isBad) return 0;
if (theNode != -1) return 1;
return ans;
}
/*
6 14
1 2
-1
1 3
-1
2 3
-1
1 0
-1
3 4
-1
2 5
-1
5 4
-1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
13 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
270 ms |
52272 KB |
Output is correct |
| 2 |
Correct |
442 ms |
59684 KB |
Output is correct |
| 3 |
Correct |
179 ms |
40276 KB |
Output is correct |
| 4 |
Incorrect |
892 ms |
78436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
13 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
13 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
13 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
