#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
using namespace std;
using namespace __gnu_pbds;
#define len(x) (int) x.size()
template<typename T>
using graph = vector<vector<T>>;
template<typename T>
using vec = vector<T>;
struct DSU {
public:
DSU() : _n(0) {}
explicit DSU(int n) : _n(n), parent_or_size(n, -1) {}
int unite(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool one(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int> &v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
int n;
graph<int> g;
DSU dsu;
bool is_zero = false;
vec<int> deg;
set<pair<int, int>> deg_sorted;
int rootb3 = -1;
int cnt3 = 0;
vec<int> roots3;
vec<bool> goods3;
vec<int> neight3;
vec<int> goodneight3;
vec<DSU> dsues;
vec<DSU> neightdsues;
vec<bool> have3;
vec<bool> have;
DSU dsu2;
int cycle_sz;
int cnt_cyc = 0;
int mx1 = 0;
int mx2 = 0;
int mx1id = -1;
void Init(int32_t N_) {
n = N_;
have.resize(n, false);
// dsu = DSU(n);
g.resize(n);
deg.resize(n);
deg_sorted.clear();
have3.resize(n);
for (int i = 0; i < n; i++) {
deg_sorted.insert({0, i});
}
dsu2 = DSU(n);
}
pair<bool, DSU> create(int v) {
DSU d = DSU(n);
for (int i = 0; i < n; i++) {
if (i == v) continue;
for (auto &j: g[i]) {
if (j == v) continue;
if (i < j) continue;
if (d.one(i, j)) {
return {false, d};
}
d.unite(i, j);
}
}
return {true, d};
}
bool add(DSU &d, int a, int b, int v) {
if (a == v or b == v) return true;
if (d.one(a, b)) return false;
d.unite(a, b);
return true;
}
void Link(int32_t a, int32_t b) {
if (is_zero)return;
if (rootb3 != -1) {
if (!add(dsu, a, b, rootb3)) {
is_zero = true;
return;
}
} else {
for (int i = 0; i < len(roots3); i++) {
if (!goods3[i]) continue;
goods3[i] = add(dsues[i], a, b, roots3[i]);
}
if (cnt3 < 3)
for (int i = 0; i < len(neight3); i++) {
if (!goodneight3[i]) continue;
goodneight3[i] = add(neightdsues[i], a, b, neight3[i]);
}
}
deg_sorted.erase({deg[a], a});
deg_sorted.erase({deg[b], b});
g[a].push_back(b);
g[b].push_back(a);
deg[a]++;
deg[b]++;
if (mx1 < deg[a]) {
mx2 = mx1;
mx1 = deg[a];
mx1id = a;
} else if (mx2 < deg[a]) {
mx2 = deg[a];
}
if (mx1 < deg[b]) {
mx2 = mx1;
mx1 = deg[b];
mx1id = b;
} else if (mx2 < deg[b]) {
mx2 = deg[b];
}
deg_sorted.insert({deg[a], a});
deg_sorted.insert({deg[b], b});
if (mx2 > 3) {
is_zero = true;
}
if (rootb3 == -1 and mx1 > 3) {
rootb3 = mx1id;
mx1 = -1;
mx2 = -1;
mx1id = -1;
for (auto &i: g[rootb3]) {
deg_sorted.erase({deg[i], i});
deg[i]--;
deg_sorted.insert({deg[i], i});
}
for(int i=0;i<n;i++){
if (mx1 < deg[i]) {
mx2 = mx1;
mx1 = deg[i];
mx1id = i;
} else if (mx2 < deg[i]) {
mx2 = deg[i];
}
}
if (n != 1 and mx2 > 2)
is_zero = true;
auto [f, d] = create(rootb3);
dsu = d;
if (!f) {
is_zero = true;
return;
}
}
if (rootb3 == -1) {
if (deg[a] == 3) {
{
cnt3++;
roots3.push_back(a);
auto [f, d] = create(a);
dsues.push_back(d);
goods3.push_back(f);
}
}
auto check = [&](int v) {
int t = 0;
for (auto u: g[v])
t += (deg[u] == 3);
return t + (deg[v] == 3) == cnt3;
};
if (deg[b] == 3) {
{
cnt3++;
roots3.push_back(b);
auto [f, d] = create(b);
dsues.push_back(d);
goods3.push_back(f);
}
if (cnt3 < 3) {
for (auto x: g[b]) {
if (have3[x] or deg[x] == 3) continue;
if (!check(x)) continue;
have3[x] = true;
neight3.push_back(x);
auto [f, d] = create(x);
neightdsues.push_back(d);
goodneight3.push_back(f);
}
}
}
if (deg[a] == 3) {
if (cnt3 < 3) {
for (auto x: g[a]) {
if (have3[x] or deg[x] == 3) continue;
if (!check(x)) continue;
have3[x] = true;
neight3.push_back(x);
auto [f, d] = create(x);
neightdsues.push_back(d);
goodneight3.push_back(f);
}
}
}
if (cnt3 > 4) {
is_zero = true;
return;
}
}
if (roots3.empty() and rootb3 == -1) {
if (dsu2.one(a, b)) {
cnt_cyc++;
cycle_sz = dsu2.size(a);
} else {
dsu2.unite(a, b);
}
if (cnt_cyc > 1) {
is_zero = true;
}
}
}
int32_t CountCritical() {
if (is_zero) return 0;
if (n == 1) return 1;
if (rootb3 != -1) {
return 1;
}
if (!roots3.empty()) {
auto check = [&](int v) {
int t = 0;
for (auto u: g[v])
t += (deg[u] == 3);
return t + (deg[v] == 3) == cnt3;
};
vec<int> can;
for (int i = 0; i < len(roots3); i++) {
if (!goods3[i]) continue;
if (have[roots3[i]]) continue;
if (!check(roots3[i])) continue;
have[roots3[i]] = true;
can.push_back(roots3[i]);
}
if (cnt3 < 3)
for (int i = 0; i < len(neight3); i++) {
if (!goodneight3[i]) continue;
if (have[neight3[i]]) continue;
if (!check(neight3[i])) continue;
have[roots3[i]] = true;
can.push_back(neight3[i]);
}
for (auto &i: can) {
have[i] = false;
}
return len(can);
}
if (cnt_cyc == 1)
return cycle_sz;
if (cnt_cyc == 0)
return n;
}
Compilation message
rings.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
rings.cpp: In function 'int32_t CountCritical()':
rings.cpp:322:1: warning: control reaches end of non-void function [-Wreturn-type]
322 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1272 ms |
57596 KB |
Output is correct |
| 2 |
Incorrect |
1538 ms |
99032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
