#include <bits/stdc++.h>
#include "rings.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
int status;
vector<int> adj[MAXN];
unordered_set<int> verts[5]; //verts[min(degree, 4)]
#define end enddd
int ntest;
struct union_find {
int exc; //vertex to be exluced
bool ok; //is this answer good?
int ncyc, szcyc; //# of cycles, size of one of the cycles if there is any.
int par[MAXN];
int start[MAXN], end[MAXN];
int nedge[MAXN]; //lol I forgot the case of CYCLES!! :(
int sz[MAXN];
void reset (int e) {
exc = e;
ok = true;
ncyc = 0;
for (int i = 0; i < N; i++) {
par[i] = i;
start[i] = i;
end[i] = i;
nedge[i] = 0;
sz[i] = 1;
}
}
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void merge (int a, int b) {
if ((!ok && status > 2) || a == exc || b == exc) {
return;
}
int fa = find(a), fb = find(b);
if (fa == fb) {
ncyc -= (sz[fa] == nedge[fa]);
nedge[fa]++;
ncyc += (sz[fa] == nedge[fa]);
if (sz[fa] == nedge[fa]) {
szcyc = sz[fa];
}
ok = false;
return;
}
if (a != end[fa]) {
swap(start[fa], end[fa]);
}
if (b != start[fb]) {
swap(start[fb], end[fb]);
}
if (a != end[fa] || b != start[fb]) {
ok = false;
return;
}
par[fb] = fa;
end[fa] = end[fb];
ncyc -= (sz[fa] == nedge[fa]);
ncyc -= (sz[fb] == nedge[fb]);
nedge[fa] = nedge[fa] + nedge[fb] + 1;
sz[fa] += sz[fb];
ncyc += (sz[fa] == nedge[fa]);
if (sz[fa] == nedge[fa]) {
assert(status >= 3);
szcyc = sz[fa];
}
}
} uf[4];
void Init (int nnnn) {
N = nnnn;
//ok now do something else
for (int i = 0; i < N; i++) {
verts[0].insert(i);
}
ntest = 1;
uf[0].reset(-1);
status = 0;
}
void settest (vector<int> v) {
ntest = v.size();
for (int i = 0; i < ntest; i++) {
uf[i].reset(v[i]);
for (int x = 0; x < N; x++) {
for (int y : adj[x]) {
if (x < y) {
uf[i].merge(x, y);
}
}
}
}
}
void Link (int a, int b) {
if (status == -1) {
return;
}
for (int v : {a, b}) {
assert(verts[min(4, (int) adj[v].size())].erase(v));
}
adj[a].push_back(b);
adj[b].push_back(a);
for (int v : {a, b}) {
verts[min(4, (int) adj[v].size())].insert(v);
}
//recalc status
status = 4;
while (verts[status].empty()) {
status--;
}
for (int i = 0; i < ntest; i++) {
uf[i].merge(a, b); //hmm "merge" is pretty bad for this case...
}
if (status == 3) {
if (ntest == 1) {
int v = *verts[3].begin();
settest(vector<int> {v, adj[v][0], adj[v][1], adj[v][2]});
}
} else if (status == 4) {
if (verts[4].size() > 1) {
status = -1;
return;
}
//otherwise, leave it to this one
if (ntest == 4) {
settest(vector<int> {*verts[4].begin()});
}
}
}
int CountCritical() {
if (status == -1) {
return 0;
}
int ans = 0;
if (status <= 2) {
if (uf[0].ncyc == 0) {
ans = N;
} else if (uf[0].ncyc == 1) {
ans = uf[0].szcyc;
} else {
ans = 0;
}
} else {
for (int i = 0; i < ntest; i++) {
ans += uf[i].ok;
}
}
if (ans == 0) {
status = -1;
}
return ans;
}
Compilation message
rings.cpp:2:10: fatal error: rings.h: No such file or directory
#include "rings.h"
^~~~~~~~~
compilation terminated.
