# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1264422 | Art | Parachute rings (IOI12_rings) | C++20 | 0 ms | 0 KiB |
// - Art -
#include <bits/stdc++.h>
#define el cout << '\n'
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i)
const int N = 1e6 + 7;
using namespace std;
struct DisjointSet {
vector<int> lab;
DisjointSet(int n = 0) {
lab.assign(n + 1, -1);
}
int findSet(int x) {
return lab[x] < 0 ? x : lab[x] = findSet(lab[x]);
}
bool unionSet(int x, int y) {
x = findSet(x), y = findSet(y);
if (x == y) {
return false;
}
if (lab[x] > lab[y]) swap(x, y);
lab[x] += lab[y];
lab[y] = x;
return true;
}
int getSize(int x) {
return -lab[findSet(x)];
}
};
struct Graph {
vector<int> deg;
int n, delNode;
int szCycle; // 0 = no cycle, -1 = more than one cycle
bool deg3;
DisjointSet dsu;
Graph() {
n = delNode = szCycle = 0;
deg3 = false;
}
Graph(int _n, int _delNode) {
n = _n;
delNode = _delNode;
szCycle = 0;
deg3 = false;
deg.assign(n + 1, 0);
dsu = DisjointSet(n);
}
void addEdge(int u, int v) {
if (u == delNode || v == delNode) {
return;
}
if (++deg[u] >= 3) {
deg3 = true;
}
if (++deg[v] >= 3) {
deg3 = true;
}
if (!dsu.unionSet(u, v)) { // u, v already in same set
int sz = dsu.getSize(u);
if (szCycle == 0) {
szCycle = sz;
}
else {
szCycle = -1;
}
}
}
bool isValid() {
return !deg3 && !szCycle;
}
int calc() {
if (szCycle == -1) {
return 0;
}
return !szCycle ? n : szCycle;
}
} whole, rem[4];
int n;
vector<int> adj[N];
int pharse = 1;
void Init(int _n) {
n = _n;
whole = Graph(_n, -1);
}
void Link(int u, int v) {
++u; ++v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
if (pharse == 1) {
if (adj[u].size() == 3 || adj[v].size() == 3) {
int tmp = adj[u].size() == 3 ? u : v;
rem[0] = Graph(n, tmp);
rem[1] = Graph(n, adj[tmp][0]);
rem[2] = Graph(n, adj[tmp][1]);
rem[3] = Graph(n, adj[tmp][2]);
FOR (u, 1, n) for (int &v : adj[u]) if (u < v) {
REP (i, 4) {
rem[i].addEdge(u, v);
}
}
pharse = 2;
}
else {
whole.addEdge(u, v);
}
}
else {
REP (i, 4) {
rem[i].addEdge(u, v);
}
}
}
int CountCritical() {
if (pharse == 1) {
return whole.calc();
}
int res = 0;
REP (i, 4) {
res += rem[i].isValid();
}
return res;
}
#ifndef ONLINE_JUDGE
int main() {
#define name "art"
if (fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// int subtask;
// cin >> subtask;
int n, q;
cin >> n >> q;
Init(n);
FOR (i, 1, q) {
int u, v;
cin >> u;
if (u == -1) {
cout << CountCritical(), el;
}
else {
cin >> v;
Link(u, v);
}
}
return 0;
}
#endif // ONLINE_JUDGE