#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("O3")
//#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 int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report \
auto end = std::chrono::high_resolution_clock::now(); \
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
{ cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;
template<typename T>
vector<T> vect(int n, T val) {
return vector<T>(n, val);
}
template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
return vector<vector<T>>(n, vector<T>(m, val));
}
template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}
template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}
template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
return matrix<T>(n, vector<T>(m, val));
}
template<typename T>
graph<T> new_graph(int n) {
return graph<T>(n);
}
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template<typename T>
using vec = vector<T>;
using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;
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<DSU> dsues;
vec<bool> have3;
void Init(i32 N_) {
n = N_;
// 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});
}
}
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(i32 a, i32 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]);
}
}
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]++;
deg_sorted.insert({deg[a], a});
deg_sorted.insert({deg[b], b});
if (n != 1 and deg_sorted.rbegin()->first > 3 and prev(prev(deg_sorted.end()))->first > 3) {
is_zero = true;
}
if (rootb3 == -1 and deg_sorted.rbegin()->first > 3) {
rootb3 = deg_sorted.rbegin()->second;
for (auto &i: g[rootb3]) {
deg_sorted.erase({deg[i], i});
deg[i]--;
deg_sorted.insert({deg[i], i});
}
if (n != 1 and prev(prev(deg_sorted.end()))->first > 2)
is_zero = true;
auto [f, d] = create(rootb3);
dsu = d;
if (!f) {
is_zero = true;
return;
}
}
if (rootb3 == -1) {
if (deg[a] == 3) {
{
have3[a] = true;
cnt3++;
roots3.push_back(a);
auto [f, d] = create(a);
dsues.push_back(d);
goods3.push_back(f);
}
for (auto x: g[a]) {
if(have3[x]) continue;
have3[x] = true;
roots3.push_back(x);
auto [f, d] = create(x);
dsues.push_back(d);
goods3.push_back(f);
}
}
if (deg[b] == 3) {
{
have3[b] = true;
cnt3++;
roots3.push_back(b);
auto [f, d] = create(b);
dsues.push_back(d);
goods3.push_back(f);
}
for (auto x: g[b]) {
if(have3[x]) continue;
roots3.push_back(x);
auto [f, d] = create(x);
dsues.push_back(d);
goods3.push_back(f);
}
}
if (cnt3 > 4) {
is_zero = true;
return;
}
}
}
i32 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;
};
set<int> can;
for (int i = 0; i < len(roots3); i++) {
if (!goods3[i]) continue;
if (!check(roots3[i])) continue;
can.insert(roots3[i]);
}
return len(can);
}
int ans = 0;
DSU d1(n);
int cnt_cyc = 0;
int tf = 0;
for (int i = 0; i < n; i++) {
for (auto &j: g[i]) {
if (i > j) continue;
if (d1.one(i, j))cnt_cyc++, tf = d1.size(i);
d1.unite(i, j);
}
}
if (cnt_cyc > 1) {
return 0;
} elif (cnt_cyc == 1) {
ans = tf;
} else ans = n;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 8 |
Correct |
6 ms |
860 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1393 ms |
69764 KB |
Output is correct |
| 2 |
Correct |
3414 ms |
133404 KB |
Output is correct |
| 3 |
Correct |
480 ms |
212276 KB |
Output is correct |
| 4 |
Execution timed out |
4043 ms |
125560 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 8 |
Correct |
6 ms |
860 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 12 |
Correct |
27 ms |
3304 KB |
Output is correct |
| 13 |
Correct |
18 ms |
2640 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1880 KB |
Output is correct |
| 15 |
Correct |
10 ms |
3492 KB |
Output is correct |
| 16 |
Correct |
23 ms |
1628 KB |
Output is correct |
| 17 |
Correct |
5 ms |
3160 KB |
Output is correct |
| 18 |
Correct |
11 ms |
5720 KB |
Output is correct |
| 19 |
Correct |
25 ms |
1692 KB |
Output is correct |
| 20 |
Correct |
19 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 8 |
Correct |
6 ms |
860 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 12 |
Correct |
27 ms |
3304 KB |
Output is correct |
| 13 |
Correct |
18 ms |
2640 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1880 KB |
Output is correct |
| 15 |
Correct |
10 ms |
3492 KB |
Output is correct |
| 16 |
Correct |
23 ms |
1628 KB |
Output is correct |
| 17 |
Correct |
5 ms |
3160 KB |
Output is correct |
| 18 |
Correct |
11 ms |
5720 KB |
Output is correct |
| 19 |
Correct |
25 ms |
1692 KB |
Output is correct |
| 20 |
Correct |
19 ms |
2396 KB |
Output is correct |
| 21 |
Execution timed out |
4061 ms |
6124 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 8 |
Correct |
6 ms |
860 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
1393 ms |
69764 KB |
Output is correct |
| 12 |
Correct |
3414 ms |
133404 KB |
Output is correct |
| 13 |
Correct |
480 ms |
212276 KB |
Output is correct |
| 14 |
Execution timed out |
4043 ms |
125560 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
