#include<bits/stdc++.h>
using namespace std;
struct DSU{
int nbGroups =0;
vector<int> anc;
vector<int> sz;
vector<pair<int, pair<int, int>>> op_buffer;
int nbCycles = 0;
int szCycle= 0;
DSU(){};
DSU(int l){
anc.resize(l);
sz.resize(l);
for(int i = 0; i<l; i++){
anc[i] = i;
sz[i] = 1;
}
nbGroups = l;
}
int c(int u){
op_buffer.push_back({u, {anc[u], sz[u]}});
if(anc[u] == u){
return u;
}
int v= c(anc[u]);
anc[u] =v;
return v;
}
void merge(int a, int b){
//cerr<<"merging "<<a<<" "<<b<<endl;
a = c(a);
b= c(b);
if(a==b){
nbCycles ++;
szCycle = sz[a];
return;
}
nbGroups--;
op_buffer.push_back({a, {anc[a], sz[a]}});
op_buffer.push_back({b, {anc[b], sz[b]}});
if(sz[a]>sz[b]){
swap(a, b);
}
anc[a] = b;
sz[b] += sz[a];
}
void undo_buffer(){
while(op_buffer.size()>0){
auto e= op_buffer.back();
if(anc[e.first] == e.first){
nbGroups--;
}
op_buffer.pop_back();
anc[e.first] = e.second.first;
sz[e.first] = e.second.second;
if(anc[e.first] == e.first){
nbGroups++;
}
}
}
};
int N;
const int MAX_N= 1e6;
vector<int> adj[MAX_N];
unordered_set<int> interesting;
bool isInteresting[MAX_N];
int deg[MAX_N], oc[MAX_N];
DSU curDSU;
int above3= 0;
int above4 = 0;
DSU recalcDSU(){
DSU newDSU(N);
for(int iV = 0; iV<N; iV++){
for(auto u: adj[iV]){
if(!(isInteresting[u] || isInteresting[iV])){
newDSU.merge(iV, u);
}
}
}
newDSU.op_buffer.clear();
return newDSU;
}
DSU beginDSU;
bool lost3 =false;
void changeDeg(int u, int d){
if(deg[u]>=3){
above3--;
}
if(deg[u] >= 4){
above4--;
}
oc[deg[u]]--;
deg[u] +=d;
oc[deg[u]] ++;
if(deg[u]>=3){
above3++;
}
if(deg[u] >= 4){
above4++;
}
}
void Init(int N_) {
N = N_;
fill(&oc[0], &oc[N], 0);
fill(&isInteresting[0], &isInteresting[N], true);
for(int i = 0; i<N; i++){
interesting.insert(i);
}
oc[0] =N;
curDSU = DSU(N);
beginDSU = DSU(N);
}
bool check_possible(){
return interesting.size()>0;
}
void updInteresting(int u){
unordered_set<int> close;
for(auto e: adj[u]){
close.insert(e);
}
close.insert(u);
for(auto it = interesting.begin(); it!=interesting.end(); ){
if(close.find(*it) == close.end()){
isInteresting[*it] = false;
//cerr<<"removing "<<*it<<endl;
for(auto ee: adj[*it]){
if(!isInteresting[ee]){
curDSU.merge(*it, ee);
}
}
it = interesting.erase(it);
}
else{
++it;
}
}
}
bool changed = true;
void clear_interesting(){
unordered_set<int> new_interesting;
for(auto e: interesting){
if(deg[e] != 4){
isInteresting[e] = false;
}
else{
new_interesting.insert(e);
}
}
for(auto e: interesting){
for(auto ee: adj[e]){
if(!(isInteresting[ee] ||isInteresting[e])){
curDSU.merge(e, ee);
}
}
}
swap(interesting, new_interesting);
}
void Link(int A, int B) {
changed = true;
if(above4>1 || lost3){
return;
}
beginDSU.merge(A, B);
adj[A].push_back(B);
changeDeg(A, +1);
adj[B].push_back(A);
changeDeg(B, +1);
if((deg[A]== 3 || deg[B]==3)){
if(deg[A] != 3){
swap(A, B);
}
updInteresting(A);
if(deg[B] == 3){
updInteresting(B);
}
if(above4 == 0){
curDSU = recalcDSU();
}
}
if(isInteresting[A] || isInteresting[B]){
}
else{
curDSU.merge(A, B);
curDSU.op_buffer.clear();
}
if((deg[A] == 4 || deg[B]== 4) && above4 == 1){
clear_interesting();
}
lost3 = !check_possible();
}
int prev_res= 0;
int calc(){
if(above4>1 || lost3){
return 0;
}
else{
if(above4 == 1){
if((oc[0]-1)*2 + oc[1] == (curDSU.nbGroups-1)*2 && above3 ==0){
return 1;
}
return 0;
}
else if(above3>=1){
int res= 0;
for(auto iAdd: interesting){
for(auto e: adj[iAdd]){
if(!isInteresting[e]){
changeDeg(e, -1);
}
changeDeg(iAdd, -1);
}
}
curDSU.op_buffer.clear();
for(auto iRem: interesting){
if(deg[iRem]>=4 || above4 ==0){
for(auto iAdd: interesting){
if(iAdd!=iRem){
for(auto e: adj[iAdd]){
if(e!=iRem){
curDSU.merge(e, iAdd);
if(!isInteresting[e]){
changeDeg(e, 1);
}
changeDeg(iAdd, 1);
}
}
}
}
curDSU.op_buffer.clear();
if((oc[0]-1)*2 + oc[1] == (curDSU.nbGroups-1)*2 && above3 ==0){
res++;
}
for(auto iAdd: interesting){
if(iAdd!=iRem){
for(auto e: adj[iAdd]){
if(e!=iRem){
if(!isInteresting[e]){
changeDeg(e, -1);
}
changeDeg(iAdd, -1);
}
}
}
}
curDSU.undo_buffer();
}
}
for(auto iAdd: interesting){
for(auto e: adj[iAdd]){
if(!isInteresting[e]){
changeDeg(e, 1);
}
changeDeg(iAdd, 1);
}
}
return res;
}
else{
if(beginDSU.nbCycles == 0){
return N;
}
else if(beginDSU.nbCycles == 1){
return beginDSU.szCycle;
}
else{
return 0;
}
}
}
}
int CountCritical() {
if(!changed){
return prev_res;
}
prev_res = calc();
return prev_res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
25248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
304 ms |
121308 KB |
Output is correct |
| 2 |
Incorrect |
782 ms |
176324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
25248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
25248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
25248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
