#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];
set <II> 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];
bool have_cycle[N];
void Init(int _n)
{
n=_n;
for(u=1;u<=n;u++) ok1.insert({ 0,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 update(int u,int k)
{
to_3[u]+=k;
if(ok1.find({ to_3[u]-k,u })==ok1.end()) return ;
ok1.erase({ to_3[u]-k,u });
ok1.insert({ to_3[u],u });
}
void Filter(int u,int v)
{
for(int x:candidate)
if((u!=x && v!=x && DS[num[x]].connect(u,v)==0) || check1(x)==0)
num[x]=-1;
vector <int> tg;
for(int x:candidate)
if(num[x]>-1) 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);
update(u,(deg[u]==3)+(deg[v]>=3));
update(v,(deg[v]==3)+(deg[u]>=3));
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(deg[u]==3)
{
for(int x:a[u])
if(x!=v) update(x,1);
}
if(deg[v]==3)
{
for(int x:a[v])
if(x!=u) update(x,1);
}
if(flag) Filter(u,v);
else
{
if(cnt4==2) ok1.clear();
if(cnt4==1)
{
set <II> tg;
for(II x:ok1)
if(check1(x.snd)) tg.insert(x);
ok1=tg;
}
while(ok1.size()>0)
{
int u=ok1.begin()->snd;
if(check1(u)) break;
ok1.erase(ok1.begin());
}
if(ok1.size()<=4)
{
flag=1;
for(II x:ok1)
{
int u=x.snd;
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 |
9 ms |
31068 KB |
Output is correct |
2 |
Correct |
12 ms |
48268 KB |
Output is correct |
3 |
Correct |
12 ms |
48220 KB |
Output is correct |
4 |
Correct |
7 ms |
31304 KB |
Output is correct |
5 |
Correct |
9 ms |
31576 KB |
Output is correct |
6 |
Correct |
12 ms |
33884 KB |
Output is correct |
7 |
Correct |
12 ms |
50012 KB |
Output is correct |
8 |
Correct |
11 ms |
33740 KB |
Output is correct |
9 |
Correct |
13 ms |
48220 KB |
Output is correct |
10 |
Correct |
14 ms |
50524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1660 ms |
99404 KB |
Output is correct |
2 |
Correct |
1906 ms |
133264 KB |
Output is correct |
3 |
Correct |
1177 ms |
127012 KB |
Output is correct |
4 |
Execution timed out |
4046 ms |
156164 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
31068 KB |
Output is correct |
2 |
Correct |
12 ms |
48268 KB |
Output is correct |
3 |
Correct |
12 ms |
48220 KB |
Output is correct |
4 |
Correct |
7 ms |
31304 KB |
Output is correct |
5 |
Correct |
9 ms |
31576 KB |
Output is correct |
6 |
Correct |
12 ms |
33884 KB |
Output is correct |
7 |
Correct |
12 ms |
50012 KB |
Output is correct |
8 |
Correct |
11 ms |
33740 KB |
Output is correct |
9 |
Correct |
13 ms |
48220 KB |
Output is correct |
10 |
Correct |
14 ms |
50524 KB |
Output is correct |
11 |
Correct |
15 ms |
48476 KB |
Output is correct |
12 |
Correct |
22 ms |
49104 KB |
Output is correct |
13 |
Correct |
20 ms |
51036 KB |
Output is correct |
14 |
Correct |
14 ms |
50524 KB |
Output is correct |
15 |
Correct |
15 ms |
49356 KB |
Output is correct |
16 |
Correct |
18 ms |
34520 KB |
Output is correct |
17 |
Correct |
14 ms |
50780 KB |
Output is correct |
18 |
Correct |
17 ms |
51276 KB |
Output is correct |
19 |
Correct |
18 ms |
34648 KB |
Output is correct |
20 |
Correct |
20 ms |
51036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
31068 KB |
Output is correct |
2 |
Correct |
12 ms |
48268 KB |
Output is correct |
3 |
Correct |
12 ms |
48220 KB |
Output is correct |
4 |
Correct |
7 ms |
31304 KB |
Output is correct |
5 |
Correct |
9 ms |
31576 KB |
Output is correct |
6 |
Correct |
12 ms |
33884 KB |
Output is correct |
7 |
Correct |
12 ms |
50012 KB |
Output is correct |
8 |
Correct |
11 ms |
33740 KB |
Output is correct |
9 |
Correct |
13 ms |
48220 KB |
Output is correct |
10 |
Correct |
14 ms |
50524 KB |
Output is correct |
11 |
Correct |
15 ms |
48476 KB |
Output is correct |
12 |
Correct |
22 ms |
49104 KB |
Output is correct |
13 |
Correct |
20 ms |
51036 KB |
Output is correct |
14 |
Correct |
14 ms |
50524 KB |
Output is correct |
15 |
Correct |
15 ms |
49356 KB |
Output is correct |
16 |
Correct |
18 ms |
34520 KB |
Output is correct |
17 |
Correct |
14 ms |
50780 KB |
Output is correct |
18 |
Correct |
17 ms |
51276 KB |
Output is correct |
19 |
Correct |
18 ms |
34648 KB |
Output is correct |
20 |
Correct |
20 ms |
51036 KB |
Output is correct |
21 |
Correct |
61 ms |
38480 KB |
Output is correct |
22 |
Correct |
88 ms |
41416 KB |
Output is correct |
23 |
Correct |
107 ms |
43484 KB |
Output is correct |
24 |
Correct |
61 ms |
56912 KB |
Output is correct |
25 |
Correct |
39 ms |
56912 KB |
Output is correct |
26 |
Correct |
58 ms |
57140 KB |
Output is correct |
27 |
Correct |
140 ms |
44232 KB |
Output is correct |
28 |
Correct |
62 ms |
56916 KB |
Output is correct |
29 |
Correct |
54 ms |
57576 KB |
Output is correct |
30 |
Correct |
186 ms |
45672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
31068 KB |
Output is correct |
2 |
Correct |
12 ms |
48268 KB |
Output is correct |
3 |
Correct |
12 ms |
48220 KB |
Output is correct |
4 |
Correct |
7 ms |
31304 KB |
Output is correct |
5 |
Correct |
9 ms |
31576 KB |
Output is correct |
6 |
Correct |
12 ms |
33884 KB |
Output is correct |
7 |
Correct |
12 ms |
50012 KB |
Output is correct |
8 |
Correct |
11 ms |
33740 KB |
Output is correct |
9 |
Correct |
13 ms |
48220 KB |
Output is correct |
10 |
Correct |
14 ms |
50524 KB |
Output is correct |
11 |
Correct |
1660 ms |
99404 KB |
Output is correct |
12 |
Correct |
1906 ms |
133264 KB |
Output is correct |
13 |
Correct |
1177 ms |
127012 KB |
Output is correct |
14 |
Execution timed out |
4046 ms |
156164 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |