#include<vector>
#include<iostream>
using namespace std;
vector<int> g[2000000];
int n,u[2000000],q[8],p[8];
int sz[2000000][8],pa[2000000][8],kq[2000000][8],ynt1[5],ynt2=-1,minchev2=1,y=0,kk[7],ee;
int CountCritical();
void crset(int a,int c)
{
sz[a][c]=1;
pa[a][c]=a;
}
int getparent(int a,int c)
{
if(pa[a][c]==a)
return a;
pa[a][c]=getparent(pa[a][c],c);
return pa[a][c];
}
void setunion(int a,int b,int c)
{
a=getparent(a,c);
b=getparent(b,c);
if(a==b)
{
q[c]++;
p[c]+=sz[a][c];
}
if(a>b)
{
sz[a][c]+=sz[b][c];
pa[b][c]=a;
}
if(a<b)
{
sz[b][c]+=sz[a][c];
pa[a][c]=b;
}
}
void Init(int N_) {
n = N_;
for(int i=0;i<n;i++)
crset(i,4);
}
void Link(int A, int B) {
g[A].push_back(B);
g[B].push_back(A);
kq[A][7]++;kq[B][7]++;
if(kq[A][7]<kq[B][7])
swap(A,B);
if(ynt2!=-1)
{
if(ynt2!=A && ynt2!=B)
{
kq[A][5]++;
kq[B][5]++;
if(kq[A][5]>2 || kq[B][5]>2)
kk[5]=1;
setunion(A,B,5);
}
}
if(kq[A][7]>=4 && ynt2==-1)
{
ynt2=A;
for(int i=0;i<n;i++)
crset(i,5);
for(int i=0;i<n;i++)
{
if(A==i)
continue;
for(int j=0;j<g[i].size();j++)
{
int to=g[i][j];
if(to==A)
continue;
if(to>i)
{
setunion(to,i,5);
kq[to][5]++;
kq[i][5]++;
if(kq[to][5]>2 || kq[i][5]>2)
kk[5]=1;
}
}
}
}
if(ynt2==-1 && minchev2==0)
{
for(int e=0;e<4;e++)
{
if(ynt1[e]==A || ynt1[e]==B)
continue;
kq[A][e]++;
kq[B][e]++;
if(kq[A][e]>2 || kq[B][e]>2)
kk[e]=1;
setunion(A,B,e);
}
}
if(kq[A][7]==3 && ynt2==-1 && minchev2==1)
{
minchev2=0;
ynt1[0]=A;
for(int i=0;i<g[A].size();i++)
ynt1[i+1]=g[A][i];
for(int e=0;e<4;e++)
{
for(int i=0;i<n;i++)
{
if(i==ynt1[e])
continue;
crset(i,e);
}
for(int i=0;i<n;i++)
{
if(i==ynt1[e])
continue;
for(int j=0;j<g[i].size();j++)
{
int to=g[i][j];
if(to==ynt1[e])
continue;
if(to>i)
{
setunion(i,to,e);
kq[to][e]++;
kq[i][e]++;
if(kq[to][e]>2 || kq[i][e]>2)
kk[e]=1;
}
}
}
}
}
if(minchev2==1)
setunion(A,B,4);
}
int CountCritical() {
if(minchev2==1)
{
if(q[4]==1)
return p[4];
if(q[4]>1)
return 0;
if(q[4]==0)
return n;
}
else if(ynt2!=-1)
{
if(q[5]==0 && kk[5]==0)
return 1;
else
return 0;
}
else
{
int u=0;
for(int e=0;e<4;e++)
{
if(q[e]==0 && kk[e]==0)
u++;
}
return u;
}
}
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[i].size();j++)
~^~~~~~~~~~~~
rings.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[A].size();i++)
~^~~~~~~~~~~~
rings.cpp:120:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[i].size();j++)
~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:168:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47352 KB |
Output is correct |
2 |
Correct |
46 ms |
47988 KB |
Output is correct |
3 |
Correct |
49 ms |
48244 KB |
Output is correct |
4 |
Correct |
43 ms |
48244 KB |
Output is correct |
5 |
Correct |
45 ms |
48244 KB |
Output is correct |
6 |
Correct |
48 ms |
48244 KB |
Output is correct |
7 |
Correct |
44 ms |
48244 KB |
Output is correct |
8 |
Correct |
46 ms |
48244 KB |
Output is correct |
9 |
Correct |
47 ms |
48244 KB |
Output is correct |
10 |
Correct |
46 ms |
48244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
657 ms |
112852 KB |
Output is correct |
2 |
Correct |
2262 ms |
147764 KB |
Output is correct |
3 |
Correct |
1851 ms |
168828 KB |
Output is correct |
4 |
Correct |
1908 ms |
173036 KB |
Output is correct |
5 |
Correct |
1756 ms |
173036 KB |
Output is correct |
6 |
Correct |
1684 ms |
173036 KB |
Output is correct |
7 |
Correct |
1650 ms |
173036 KB |
Output is correct |
8 |
Correct |
2814 ms |
173036 KB |
Output is correct |
9 |
Correct |
3220 ms |
173036 KB |
Output is correct |
10 |
Correct |
1097 ms |
173036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47352 KB |
Output is correct |
2 |
Correct |
46 ms |
47988 KB |
Output is correct |
3 |
Correct |
49 ms |
48244 KB |
Output is correct |
4 |
Correct |
43 ms |
48244 KB |
Output is correct |
5 |
Correct |
45 ms |
48244 KB |
Output is correct |
6 |
Correct |
48 ms |
48244 KB |
Output is correct |
7 |
Correct |
44 ms |
48244 KB |
Output is correct |
8 |
Correct |
46 ms |
48244 KB |
Output is correct |
9 |
Correct |
47 ms |
48244 KB |
Output is correct |
10 |
Correct |
46 ms |
48244 KB |
Output is correct |
11 |
Correct |
47 ms |
173036 KB |
Output is correct |
12 |
Correct |
51 ms |
173036 KB |
Output is correct |
13 |
Correct |
51 ms |
173036 KB |
Output is correct |
14 |
Correct |
47 ms |
173036 KB |
Output is correct |
15 |
Correct |
48 ms |
173036 KB |
Output is correct |
16 |
Correct |
48 ms |
173036 KB |
Output is correct |
17 |
Correct |
51 ms |
173036 KB |
Output is correct |
18 |
Correct |
51 ms |
173036 KB |
Output is correct |
19 |
Correct |
48 ms |
173036 KB |
Output is correct |
20 |
Correct |
50 ms |
173036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47352 KB |
Output is correct |
2 |
Correct |
46 ms |
47988 KB |
Output is correct |
3 |
Correct |
49 ms |
48244 KB |
Output is correct |
4 |
Correct |
43 ms |
48244 KB |
Output is correct |
5 |
Correct |
45 ms |
48244 KB |
Output is correct |
6 |
Correct |
48 ms |
48244 KB |
Output is correct |
7 |
Correct |
44 ms |
48244 KB |
Output is correct |
8 |
Correct |
46 ms |
48244 KB |
Output is correct |
9 |
Correct |
47 ms |
48244 KB |
Output is correct |
10 |
Correct |
46 ms |
48244 KB |
Output is correct |
11 |
Correct |
47 ms |
173036 KB |
Output is correct |
12 |
Correct |
51 ms |
173036 KB |
Output is correct |
13 |
Correct |
51 ms |
173036 KB |
Output is correct |
14 |
Correct |
47 ms |
173036 KB |
Output is correct |
15 |
Correct |
48 ms |
173036 KB |
Output is correct |
16 |
Correct |
48 ms |
173036 KB |
Output is correct |
17 |
Correct |
51 ms |
173036 KB |
Output is correct |
18 |
Correct |
51 ms |
173036 KB |
Output is correct |
19 |
Correct |
48 ms |
173036 KB |
Output is correct |
20 |
Correct |
50 ms |
173036 KB |
Output is correct |
21 |
Correct |
70 ms |
173036 KB |
Output is correct |
22 |
Correct |
95 ms |
173036 KB |
Output is correct |
23 |
Correct |
105 ms |
173036 KB |
Output is correct |
24 |
Correct |
113 ms |
173036 KB |
Output is correct |
25 |
Correct |
71 ms |
173036 KB |
Output is correct |
26 |
Correct |
116 ms |
173036 KB |
Output is correct |
27 |
Correct |
116 ms |
173036 KB |
Output is correct |
28 |
Correct |
125 ms |
173036 KB |
Output is correct |
29 |
Correct |
98 ms |
173036 KB |
Output is correct |
30 |
Correct |
148 ms |
173036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47352 KB |
Output is correct |
2 |
Correct |
46 ms |
47988 KB |
Output is correct |
3 |
Correct |
49 ms |
48244 KB |
Output is correct |
4 |
Correct |
43 ms |
48244 KB |
Output is correct |
5 |
Correct |
45 ms |
48244 KB |
Output is correct |
6 |
Correct |
48 ms |
48244 KB |
Output is correct |
7 |
Correct |
44 ms |
48244 KB |
Output is correct |
8 |
Correct |
46 ms |
48244 KB |
Output is correct |
9 |
Correct |
47 ms |
48244 KB |
Output is correct |
10 |
Correct |
46 ms |
48244 KB |
Output is correct |
11 |
Correct |
657 ms |
112852 KB |
Output is correct |
12 |
Correct |
2262 ms |
147764 KB |
Output is correct |
13 |
Correct |
1851 ms |
168828 KB |
Output is correct |
14 |
Correct |
1908 ms |
173036 KB |
Output is correct |
15 |
Correct |
1756 ms |
173036 KB |
Output is correct |
16 |
Correct |
1684 ms |
173036 KB |
Output is correct |
17 |
Correct |
1650 ms |
173036 KB |
Output is correct |
18 |
Correct |
2814 ms |
173036 KB |
Output is correct |
19 |
Correct |
3220 ms |
173036 KB |
Output is correct |
20 |
Correct |
1097 ms |
173036 KB |
Output is correct |
21 |
Correct |
47 ms |
173036 KB |
Output is correct |
22 |
Correct |
51 ms |
173036 KB |
Output is correct |
23 |
Correct |
51 ms |
173036 KB |
Output is correct |
24 |
Correct |
47 ms |
173036 KB |
Output is correct |
25 |
Correct |
48 ms |
173036 KB |
Output is correct |
26 |
Correct |
48 ms |
173036 KB |
Output is correct |
27 |
Correct |
51 ms |
173036 KB |
Output is correct |
28 |
Correct |
51 ms |
173036 KB |
Output is correct |
29 |
Correct |
48 ms |
173036 KB |
Output is correct |
30 |
Correct |
50 ms |
173036 KB |
Output is correct |
31 |
Correct |
70 ms |
173036 KB |
Output is correct |
32 |
Correct |
95 ms |
173036 KB |
Output is correct |
33 |
Correct |
105 ms |
173036 KB |
Output is correct |
34 |
Correct |
113 ms |
173036 KB |
Output is correct |
35 |
Correct |
71 ms |
173036 KB |
Output is correct |
36 |
Correct |
116 ms |
173036 KB |
Output is correct |
37 |
Correct |
116 ms |
173036 KB |
Output is correct |
38 |
Correct |
125 ms |
173036 KB |
Output is correct |
39 |
Correct |
98 ms |
173036 KB |
Output is correct |
40 |
Correct |
148 ms |
173036 KB |
Output is correct |
41 |
Correct |
357 ms |
173036 KB |
Output is correct |
42 |
Correct |
1313 ms |
173036 KB |
Output is correct |
43 |
Correct |
479 ms |
173036 KB |
Output is correct |
44 |
Correct |
1176 ms |
173036 KB |
Output is correct |
45 |
Correct |
1335 ms |
173036 KB |
Output is correct |
46 |
Correct |
1041 ms |
173036 KB |
Output is correct |
47 |
Correct |
1425 ms |
173036 KB |
Output is correct |
48 |
Correct |
836 ms |
173036 KB |
Output is correct |
49 |
Correct |
1016 ms |
173036 KB |
Output is correct |
50 |
Correct |
1104 ms |
173036 KB |
Output is correct |
51 |
Correct |
496 ms |
173036 KB |
Output is correct |
52 |
Correct |
980 ms |
173036 KB |
Output is correct |
53 |
Correct |
850 ms |
173036 KB |
Output is correct |
54 |
Correct |
2184 ms |
173036 KB |
Output is correct |
55 |
Correct |
1619 ms |
173036 KB |
Output is correct |