#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 1000005
using namespace std;
struct International_Olympiad_in_Informatics
{
struct DSU
{
int r[N];
int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
void Init()
{
for(int u=1;u<N;u++) r[u]=u;
}
bool connect(int u,int v)
{
u=root(u); v=root(v);
if(u==v) return 0;
r[u]=v;
return 1;
}
} DS[4];
vector <II> edge;
vector <int> candidate,a[N],ok1;
int n,i,u,v,flag,cnt3,cnt4,int4,deg[N],to_3[N],num[N],n_ring,w_ring,node[N],node3[N],r[N],now[N],step;
bool have_cycle[N];
void Init(int _n)
{
n=_n;
for(u=1;u<=n;u++) ok1.push_back(u),r[u]=u,node[u]=1;
}
bool check1(int u)
{
if(cnt4==2) return 0;
if(cnt4==1 && deg[u]<4) return 0;
return (to_3[u]==cnt3);
}
void Filter(int u,int v)
{
vector <int> tg;
for(int x:candidate)
if(!((u!=x && v!=x && DS[num[x]].connect(u,v)==0) || check1(x)==0))
tg.push_back(x);
candidate=tg;
return ;
}
int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
void check_root(int u,int op)
{
if(have_cycle[u]==1 && node3[u]==0)
n_ring+=op,w_ring+=op*node[u];
}
void join(int u,int v)
{
u=root(u); v=root(v);
if(u==v)
{
check_root(u,-1);
have_cycle[u]=1;
check_root(u,1);
return ;
}
check_root(u,-1);
check_root(v,-1);
r[u]=v;
node3[v]+=node3[u];
node[v]+=node[u];
have_cycle[v]|=have_cycle[u];
check_root(v,1);
}
void Link(int u,int v)
{
// cerr<<u<<" "<<v<<'\n';
edge.push_back({ u,v });
a[u].push_back(v); a[v].push_back(u);
deg[u]++; deg[v]++;
cnt3+=(deg[u]==3)+(deg[v]==3);
cnt4+=(deg[u]==4)+(deg[v]==4);
check_root(root(u),-1);
node3[root(u)]+=(deg[u]==3);
check_root(root(u),1);
check_root(root(v),-1);
node3[root(v)]+=(deg[v]==3);
check_root(root(v),1);
join(u,v);
if(flag) Filter(u,v);
else
{
if(cnt4==2) { step++; ok1.clear(); }
if(cnt4==1)
{
step++;
vector <int> tg;
for(int u:ok1)
if(check1(u)) tg.push_back(u),now[u]=step;
ok1=tg;
}
if(deg[u]==3 || deg[v]==3)
{
step++;
vector <int> tg;
if(deg[u]==3)
{
for(int x:a[u])
if(now[x]==step-1 && check1(x)) now[x]=step,tg.push_back(x);
if(now[u]==step-1 && check1(u)) now[u]=step,tg.push_back(u);
}
if(deg[v]==3)
{
for(int x:a[v])
if(now[x]==step-1 && check1(x)) now[x]=step,tg.push_back(x);
if(now[v]==step-1 && check1(v)) now[v]=step,tg.push_back(v);
}
ok1=tg;
}
if(ok1.size()<=4)
{
flag=1;
for(int u:ok1)
{
num[u]=candidate.size();
candidate.push_back(u);
DS[num[u]].Init();
}
for(II x:edge) Filter(x.fst,x.snd);
}
}
}
int Cal()
{
if(n_ring>1) return 0;
if(n_ring==1)
{
if(cnt3>0) return 0;
return w_ring;
}
return (flag==0) ? ok1.size() : candidate.size();
}
} IOI;
void Init(int _n) { IOI.Init(_n); }
void Link(int u,int v) { IOI.Link(u+1,v+1); }
int CountCritical() { return IOI.Cal(); }
int n,u,v,type,q;
/*
int main()
{
freopen("rings.inp","r",stdin);
freopen("rings.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>q; Init(n);
while(q--)
{
cin>>u;
if(u>-1) cin>>v,Link(u,v);
else cout<<CountCritical()<<'\n';
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
31064 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
66300 KB |
Output is correct |
| 2 |
Incorrect |
651 ms |
86556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
31064 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
31064 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
31064 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
