#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >hist;
void Link(int A,int B);
void Init(int _N);
const int MAXN=1e6+6;
set<int>g_with_big[MAXN];
set<int>g_without_big[MAXN];
bool found_big=0;
bool ans0=0;
int big;
set<pair<int,int> >nodes;
int par[MAXN];
int sz[MAXN];
set<int>with_sz[MAXN];
int cnt_comp=1;
int N;
bool cycle[MAXN];
void init()
{
cnt_comp=N;
memset(cycle,0,sizeof(cycle));
memset(sz,1,sizeof(sz));
for(int i=0;i<MAXN;i++)par[i]=i;
}
void join(int p,int q)
{
cnt_comp--;
if(sz[p]>sz[q])
{
par[q]=p;
sz[p]+=sz[q];
}
else
{
par[p]=q;
sz[q]+=sz[p];
}
}
int getRoot(int u)
{
if(u==par[u])return u;
return par[u]=getRoot(par[u]);
}
void rmv_big(int u)
{
big=u;
Init(N);
for(int i=0;i<MAXN;i++)g_without_big[i].clear();
for(int i=0;i<MAXN;i++)g_with_big[i].clear();
for(auto xd:hist)
{
if(xd.first==u)continue;
if(xd.second==u)continue;
Link(xd.first,xd.second);
}
}
bool check()
{
return with_sz[1].size()/2+with_sz[0].size()==cnt_comp&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()==N;
}
void Init(int _N)
{
N=_N;
init();
for(int i=0;i<N;i++)with_sz[0].insert(i);
}
void Link(int A, int B) {
if(ans0)return;
if(found_big==0)
{
with_sz[g_without_big[A].size()].erase(A);
with_sz[g_without_big[B].size()].erase(B);
g_without_big[A].insert(B);
g_without_big[B].insert(A);
g_with_big[A].insert(B);
g_with_big[B].insert(A);
with_sz[g_without_big[A].size()].insert(A);
with_sz[g_without_big[B].size()].insert(B);
if(g_without_big[A].size()>3&&g_without_big[A].size()>3)
{
ans0=1;
return;
}
int a=getRoot(A),b=getRoot(B);
if(a!=b)join(a,b);
if(a==b)cycle[a]=1;
if(g_without_big[A].size()>3)
{
rmv_big(A);
}
if(g_without_big[B].size()>3)
{
rmv_big(B);
}
}
else
{
with_sz[g_without_big[A].size()].erase(A);
with_sz[g_without_big[B].size()].erase(B);
if(A!=big&&B!=big)
{
g_without_big[A].insert(B);
g_without_big[B].insert(A);
g_with_big[A].insert(B);
g_with_big[B].insert(A);
}
else
{
g_with_big[A].insert(B);
g_with_big[B].insert(A);
}
if(A!=big)with_sz[g_without_big[A].size()].insert(A);
if(B!=big)with_sz[g_without_big[B].size()].insert(B);
int a=getRoot(A),b=getRoot(B);
if(a!=b&&A!=big&&B!=big)join(a,b);
if(a==b)cycle[a]=1;
if(g_without_big[A].size()>2&&A!=big)
{
ans0=1;
return;
}
if(g_without_big[B].size()>2&&B!=big)
{
ans0=1;
return;
}
}
hist.push_back({A,B});
}
int CountCritical() {
//cout<<"eho0\n";
if(ans0)return 0;
//cout<<"eho1\n";
if(check())
{
return N;
}
//cout<<"eho2\n";
if(with_sz[3].size()==0)
{
ans0=1;
return 0;
}
if(with_sz[3].size()>4)
{
ans0=1;
return 0;
}
//cout<<"eho3\n";
if(with_sz[3].size()==1)
{
int node=(*with_sz[3].begin());
if(cycle[getRoot(node)])return 3;
else return 4;
}
if(with_sz[3].size()==2)
{
auto it = with_sz[3].begin();
int a1=(*it);it++;int a2=(*it);
if(g_without_big[a1].find(a2)==g_without_big[a1].end())
{
ans0=0;
return 0;
}
int cnt_common=0;
for(auto xd:g_without_big[a1])
{
if(g_without_big[a2].find(xd)!=g_without_big[a2].end())cnt_common++;
}
if(cnt_common==0)
{
return 2;
}
if(cnt_common==1)return 3;
return 2;
}
//cout<<"eho4\n";
if(with_sz[3].size()==4)
{
ans0=1;return 0;
}
//cout<<"eho5\n";
auto it = with_sz[3].begin();
int a1=(*it);it++;
int a2=(*it);it++;
int a3=(*it);
int cnte=0;
if(g_without_big[a1].find(a2)!=g_without_big[a1].end())cnte++;
if(g_without_big[a1].find(a3)!=g_without_big[a1].end())cnte++;
if(g_without_big[a3].find(a2)!=g_without_big[a3].end())cnte++;
if(cnte==3)return 3;
if(cnte==2)return 1;
ans0=1;
return 0;
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/
Compilation message
rings.cpp: In function 'bool check()':
rings.cpp:61:49: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | return with_sz[1].size()/2+with_sz[0].size()==cnt_comp&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()==N;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
rings.cpp:61:138: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | return with_sz[1].size()/2+with_sz[0].size()==cnt_comp&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()==N;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
149900 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
150776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1872 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
149900 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
150776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
149900 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
150776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
149900 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
150776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
