#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 boringDSU, fullDSU;
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;
}
int state = 0;
//0 = only deg<=2
//1 only deg <=3, some interesting left
//2 One deg =4, some interesting
//3 no interesting left
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;
boringDSU = DSU(N);
fullDSU = DSU(N);
}
void updInteresting(int u, bool tolerant){
unordered_set<int> close;
if(tolerant){
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]){
boringDSU.merge(*it, ee);
}
}
it = interesting.erase(it);
}
else{
++it;
}
}
}
void recalcDeg(){
for(int i = 0; i<N; i++){
if(deg[i] != 4){
for(auto v: adj[i]){
if(deg[v] == 4){
changeDeg(i, -1);
}
}
}
}
}
void Link(int A, int B) {
if(interesting.size()== 0){
return;
}
fullDSU.merge(A, B);
adj[A].push_back(B);
adj[B].push_back(A);
if(deg[A] <4 && deg[B] < 4){
changeDeg(A, +1);
changeDeg(B, +1);
}
if((deg[A]== 3 || deg[B]==3)){
if(deg[A] != 3){
swap(A, B);
}
updInteresting(A, true);
if(deg[B] == 3){
updInteresting(B, true);
}
}
if(isInteresting[A] || isInteresting[B]){
}
else{
boringDSU.merge(A, B);
boringDSU.op_buffer.clear();
}
if((deg[A] == 4 || deg[B]== 4) && above4 == 1){
if(deg[A] != 4){
swap(A, B);
}
updInteresting(A, false);
if(deg[B] == 4){
updInteresting(B, false);
}
recalcDeg();
}
}
int prev_res= 0;
int calc(){
if(interesting.size() == 0){
return 0;
}
else{
if(above4 == 1){
if((oc[0])*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==1){
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);
}
}
boringDSU.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){
boringDSU.merge(e, iAdd);
if(!isInteresting[e]){
changeDeg(e, 1);
}
changeDeg(iAdd, 1);
}
}
}
}
if((oc[0]-1)*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==0){
res++;
//cerr<<iRem<<endl;
}
else{
//cerr<<oc[0]<<" "<<oc[1]<<" "<<oc[2]<<endl;
}
for(auto iAdd: interesting){
if(iAdd!=iRem){
for(auto e: adj[iAdd]){
if(e!=iRem){
if(!isInteresting[e]){
changeDeg(e, -1);
}
changeDeg(iAdd, -1);
}
}
}
}
boringDSU.undo_buffer();
}
}
for(auto iAdd: interesting){
for(auto e: adj[iAdd]){
if(!isInteresting[e]){
changeDeg(e, 1);
}
changeDeg(iAdd, 1);
}
}
return res;
}
else{
if(fullDSU.nbCycles == 0){
return N;
}
else if(fullDSU.nbCycles == 1){
return fullDSU.szCycle;
}
else{
return 0;
}
}
}
}
int CountCritical() {
//cerr<<oc[0]<<" "<<oc[1]<<" "<<oc[2]<<" "<<oc[3]<<endl;
prev_res = calc();
return prev_res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
13 ms |
25432 KB |
Output is correct |
| 3 |
Runtime error |
34 ms |
50516 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
127164 KB |
Output is correct |
| 2 |
Runtime error |
3136 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
13 ms |
25432 KB |
Output is correct |
| 3 |
Runtime error |
34 ms |
50516 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
13 ms |
25432 KB |
Output is correct |
| 3 |
Runtime error |
34 ms |
50516 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
13 ms |
25432 KB |
Output is correct |
| 3 |
Runtime error |
34 ms |
50516 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
