#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#ifndef mlocal
//#include "grader.h"
//#endif
#define endl '\n'
// TODO: check if at max one component is bad
vector<vi> adj, ct;
vi oc, tc, sz;
vector<bool> isCrit, isBadComp;
int crit = 0, n, over = 0, bct = 0, badComp = 0;
bool badFound = false, dunCheck = false;
class UFDS {
public:
vi p, rank; int count = 0;
void build() {
p.resize(n); rank.resize(n);
for_(i, 0, n) p[i] = i;
count = n;
}
int getParent(int i) {
return (p[i] == i) ? i : (p[i] = getParent(p[i]));
}
void setBad(int i) {
// cout << "oof bad " << oc[i] << " " << tc[i] << " " << sz[i] << endl;
isBadComp[i] = true; badComp++;
if (badComp > 1) {
crit = 0;
dunCheck = true;
}
}
void check(int i) {
i = getParent(i);
if (isBadComp[i]) return;
if (oc[i] != 2 or oc[i]+tc[i] != sz[i]) setBad(i);
}
void join(int i, int j) {
int a = getParent(i), b = getParent(j);
if (a != b) {
count -= 1;
oc[a] = oc[b] = oc[a]+oc[b];
tc[a] = tc[b] = tc[a]+tc[b];
sz[a] = sz[b] = sz[a]+sz[b];
isBadComp[a] = isBadComp[b] = isBadComp[a] or isBadComp[b];
if (rank[a] > rank[b]) {
p[b] = a;
} else {
p[a] = b;
if (rank[a] == rank[b]) rank[b] += 1;
}
}
check(a);
}
};
UFDS ufds;
void updateAdj(int p) {
int k = adj[p].size(), pp = ufds.getParent(p);
if (k == 4) over++;
else if (k == 3) {
bct++;
tc[pp]--;
}
else if (k == 2) {
oc[pp]--;
tc[pp]++;
// cout << "removing oc " << p << endl;
}
else if (k == 1) {
oc[pp]++;
// cout << "adding oc " << p << endl;
}
if (k > 3) return;
for_(i, 0, adj[p].size()) {
if (i != (int) adj[p].size()-1) ct[adj[p][i]][k-1] -= 1;
ct[adj[p][i]][k] += 1;
}
}
void find(int p) {
int k = adj[p].size();
if (k > 3) return;
if (badComp and !isBadComp[ufds.getParent(p)]) return;
for (auto i: adj[p]) {
bool temp = ct[i][3] == bct and ct[i][2] >= (2-oc[ufds.getParent(i)]);
if (temp and !isCrit[i]) crit++;
else if (!temp and isCrit[i]) crit--;
isCrit[i] = temp;
}
}
void Init(int N) {
n = N;
ufds.build(); adj.resize(n); ct.resize(n, vi(4)); isCrit.resize(n); oc.resize(n); isBadComp.resize(n); sz.resize(n, 1); tc.resize(n);
}
void Link(int a, int b) {
if (dunCheck) return;
adj[a].push_back(b); adj[b].push_back(a);
updateAdj(a); updateAdj(b);
ufds.join(a, b);
if (over > 1) {
crit = 0;
dunCheck = true;
}
if (dunCheck) return;
find(a); find(b);
}
int CountCritical() {
if (badComp == 0) return n;
else return crit;
}
//int main() {
//#ifdef mlocal
// freopen("test.in", "r", stdin);
//#endif
//
// ios_base::sync_with_stdio(false);
// cin.tie(0);
//
//// Init(7);
//// cout << CountCritical() << endl;
//// Link(1, 2);
//// cout << CountCritical() << endl;
//// Link(0, 5);
//// cout << CountCritical() << endl;
//// Link(2, 0);
//// cout << CountCritical() << endl;
//// Link(3, 2);
//// cout << CountCritical() << endl;
//// Link(3, 5);
//// cout << CountCritical() << endl;
//// Link(4, 3);
//// cout << CountCritical() << endl;
//
// Init(7);
// cout << CountCritical() << endl;
// Link(0, 1);
// cout << CountCritical() << endl;
// Link(1, 2);
// cout << CountCritical() << endl;
// Link(0, 2);
// cout << CountCritical() << endl;
// Link(3, 4);
// cout << CountCritical() << endl;
// Link(4, 5);
// cout << CountCritical() << endl;
// Link(3, 5);
// cout << CountCritical() << endl;
//
// return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
947 ms |
74604 KB |
Output is correct |
| 2 |
Incorrect |
1660 ms |
114652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
