#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
if (_split)
cerr << ", ";
cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
cerr << '[';
for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
vector<vector<int>> deg, pa, g;
vector<bool> fail;
vector<int> v, sz;
map<int, int> id;
int n, ans;
int extend() {
deg.emplace_back(n, 0);
pa.emplace_back(n);
iota(all(pa.back()), 0);
fail.push_back(false);
return deg.size() - 1;
}
int find(int _id, int i) {
return pa[_id][i] = pa[_id][i] == i ? i : find(_id, pa[_id][i]);
}
void upd(vector<int> tmp) {
if (fail[0])
return;
if (v.empty()) {
v = tmp;
return;
}
for (int i = 0; i < (int)v.size(); ) {
bool find = false;
for (int j : tmp)
if (v[i] == j)
find = true;
if (!find)
swap(v[i], v.back()), v.pop_back();
else
++i;
}
if (v.empty())
fail[0] = true;
}
void add(int _id, pi _e) {
if (fail[_id])
return;
int x = _e.first, y = _e.second;
if (++deg[_id][x] >= 3) {
fail[_id] = true;
return;
}
if (++deg[_id][y] >= 3) {
fail[_id] = true;
return;
}
x = find(_id, x), y = find(_id, y);
if (x == y) {
fail[_id] = true;
return;
}
pa[_id][x] = y;
}
struct seg {
int l, r;
vector<pi> g;
seg *ch[2]{};
seg(int _l, int _r) : l(_l), r(_r) {
if (l < r - 1)
ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
}
void modify(int _l, int _r, pi _e) {
if (_l >= _r)
return;
if (_l <= l && r <= _r) {
g.push_back(_e);
return;
}
push();
if (_l < l + r >> 1)
ch[0]->modify(_l, _r, _e);
if (l + r >> 1 < _r)
ch[1]->modify(_l, _r, _e);
}
void push() {
if (!g.empty()) {
ch[0]->g.insert(ch[0]->g.end(), all(g));
ch[1]->g.insert(ch[1]->g.end(), all(g));
g.clear();
}
}
void build(int i) {
if (l == r - 1) {
if (!id.count(i))
id[i] = extend();
while (!g.empty())
add(id[i], g.back()), g.pop_back();
return;
}
push();
ch[i >= l + r >> 1]->build(i);
}
} *rt;
void Init(int N) {
ans = n = N;
extend();
g.resize(n);
sz.assign(n, 1);
rt = new seg(0, n);
}
void Link(int x, int y) {
if (fail[0])
return;
++deg[0][x], ++deg[0][y];
g[x].push_back(y), g[y].push_back(x);
if (x > y)
swap(x, y);
rt->modify(0, x, pi(x, y));
rt->modify(x + 1, y, pi(x, y));
rt->modify(y + 1, n, pi(x, y));
if (deg[0][x] == 4) {
vector<int> tmp(1, x);
upd(tmp);
}
else if (deg[0][x] == 3) {
vector<int> tmp = g[x];
tmp.push_back(x);
upd(tmp);
}
if (deg[0][y] == 4) {
vector<int> tmp(1, y);
upd(tmp);
}
else if (deg[0][y] == 3) {
vector<int> tmp = g[y];
tmp.push_back(y);
upd(tmp);
}
x = find(0, x), y = find(0, y);
if (x == y) {
if (!fail[0] && v.empty()) {
if (ans == n)
ans = sz[x];
else
ans = 0;
}
}
else
pa[0][x] = y, sz[y] += sz[x];
}
int CountCritical() {
if (fail[0])
return 0;
if (v.empty())
return ans;
vector<int> tmp;
for (int i : v) {
rt->build(i);
if (!fail[id[i]])
tmp.push_back(i);
}
upd(tmp);
return v.size();
}
Compilation message
rings.cpp: In constructor 'seg::seg(int, int)':
rings.cpp:104:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
104 | ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
| ~~^~~
rings.cpp:104:63: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
104 | ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
| ~~^~~
rings.cpp: In member function 'void seg::modify(int, int, pi)':
rings.cpp:114:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | if (_l < l + r >> 1)
| ~~^~~
rings.cpp:116:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
116 | if (l + r >> 1 < _r)
| ~~^~~
rings.cpp: In member function 'void seg::build(int)':
rings.cpp:135:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | ch[i >= l + r >> 1]->build(i);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
178 ms |
212828 KB |
Output is correct |
| 3 |
Runtime error |
199 ms |
262148 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
153 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
178 ms |
212828 KB |
Output is correct |
| 3 |
Runtime error |
199 ms |
262148 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
178 ms |
212828 KB |
Output is correct |
| 3 |
Runtime error |
199 ms |
262148 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
178 ms |
212828 KB |
Output is correct |
| 3 |
Runtime error |
199 ms |
262148 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
