#include <vector>
#include <numeric>
#include <array>
#include <algorithm>
using namespace std;
struct DSU
{
int n, comps;
vector<int> parent, size;
vector<int> adj;
array<int, 5> counter;
int res, v;
DSU(int n = 0, int v = -1) : n(n), v(v)
{
parent.resize(n);
size.resize(n, 1);
iota(parent.begin(), parent.end(), 0);
comps = n;
adj.resize(n);
counter.fill(0);
counter[0] = n;
res = (v == -1 ? n : 1);
}
int getParent(int i)
{
if (parent[i] == i) return i;
return parent[i] = getParent(parent[i]);
}
void unite(int a, int b)
{
if (res == 0) return;
if (a == v || b == v) return;
int wasCyc = comps - counter[0] - 2 * counter[1];
--counter[min(adj[a], 4)];
--counter[min(adj[b], 4)];
++adj[a];
++adj[b];
++counter[min(adj[a], 4)];
++counter[min(adj[b], 4)];
if (counter[3] + counter[4] > 0)
{
res = 0;
return;
}
a = getParent(a);
b = getParent(b);
if (a != b) --comps;
int newCyc = comps - counter[0] - 2 * counter[1];
if (v != -1 && newCyc > 0)
{
res = 0;
return;
}
else if (v == -1)
{
if (newCyc >= 2)
{
res = 0;
return;
}
if (newCyc == 1 && wasCyc == 0)
{
vector<int> cnt(n);
for (int i = 0; i < n; ++i)
{
if (adj[i] < 2) cnt[getParent(i)] = -1e9;
else ++cnt[getParent(i)];
}
res = 0;
for (int i = 0; i < n; ++i) res = max(res, cnt[i]);
}
}
if (a != b)
{
if (size[a] < size[b]) swap(a, b);
size[a] += size[b];
parent[b] = a;
}
}
};
int n;
vector<vector<int>> adj;
array<DSU, 8> dsu;
array<int, 5> counter;
vector<int> curs, dop;
vector<pair<int, int>> edges;
void Init(int N_)
{
n = N_;
adj.resize(n);
dsu[0] = DSU(n);
counter[0] = n;
curs.push_back(-1);
}
void Link(int a, int b)
{
int was3 = counter[3], was4 = counter[4];
--counter[min((int)adj[a].size(), 4)];
--counter[min((int)adj[b].size(), 4)];
adj[a].push_back(b);
adj[b].push_back(a);
++counter[min((int)adj[a].size(), 4)];
++counter[min((int)adj[b].size(), 4)];
if (counter[4] > 1) return;
if (counter[4] > was4)
{
curs.clear();
dop.clear();
for (int i = 0; i < 7; ++i) dsu[i].res = 0;
if (adj[a].size() == 4) curs.push_back(a);
if (adj[b].size() == 4) curs.push_back(b);
dsu[0] = DSU(n, curs[0]);
for (auto [a, b] : edges) dsu[0].unite(a, b);
}
else if (counter[3] > was3)
{
if (counter[3] > 4 && was3 <= 4)
{
curs.clear();
dop.clear();
for (int i = 0; i < 7; ++i) dsu[i].res = 0;
}
if (counter[3] <= 4)
{
if (was3 == 0) curs.clear();
if (adj[a].size() == 3) curs.push_back(a);
if (adj[b].size() == 3) curs.push_back(b);
for (int i = 0; i < 7; ++i) dsu[i].res = 0;
dop.clear();
for (int i = 0; i < curs.size(); ++i)
{
dsu[i] = DSU(n, curs[i]);
for (auto [a, b]: edges) dsu[i].unite(a, b);
}
//calc dop
if (curs.size() < 3)
{
for (int i = 0; i < n; ++i)
{
if (adj[i].size() < 3)
{
bool was0 = false, was1 = curs.size() == 1;
for (int j: adj[i])
{
was0 = was0 || (j == curs[0]);
if (curs.size() == 2) was1 = was0 || (j == curs[1]);
}
if (was0 && was1)
{
dop.push_back(i);
}
}
}
}
for (int i = 0; i < dop.size(); ++i)
{
dsu[i + curs.size()] = DSU(n, dop[i]);
for (auto [a, b]: edges) dsu[i + curs.size()].unite(a, b);
}
}
}
for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b);
for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
edges.emplace_back(a, b);
}
int CountCritical()
{
if (counter[4] > 1) return 0;
int res = 0;
for (int i = 0; i < 7; ++i) res += dsu[i].res;
return res;
}
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:139:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int i = 0; i < curs.size(); ++i)
| ~~^~~~~~~~~~~~~
rings.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (int i = 0; i < dop.size(); ++i)
| ~~^~~~~~~~~~~~
rings.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b);
| ~~^~~~~~~~~~~~~
rings.cpp:172:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
848 KB |
Output is correct |
| 3 |
Correct |
3 ms |
852 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
458 ms |
39476 KB |
Output is correct |
| 2 |
Correct |
1177 ms |
88992 KB |
Output is correct |
| 3 |
Correct |
733 ms |
122704 KB |
Output is correct |
| 4 |
Incorrect |
1012 ms |
75028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
848 KB |
Output is correct |
| 3 |
Correct |
3 ms |
852 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
848 KB |
Output is correct |
| 3 |
Correct |
3 ms |
852 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
848 KB |
Output is correct |
| 3 |
Correct |
3 ms |
852 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
