#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
#define fi first
#define se second
const int MX = (int)(1e6+3);
typedef pair<int,int> ii;
int N,deg[6][MX],p[6][MX],s[6][MX],pot[4],k,len;
vector<int> vec[MX],G;
vector<ii> edges;
multiset<int,greater<int> > myset;
bool flag2,flag3,flag4,st,cycle,ok[5];
bitset<MX> vis;
void Init(int N_) {
N = N_;
for (int j = 0; j < 6; ++j)
for (int i = 0; i < N; ++i)
p[j][i]=i,s[j][i]=1;
}
int findSet(int idx,int i){
if(p[idx][i]==i)return i;
return p[idx][i]=findSet(idx,p[idx][i]);
}
bool Union(int idx,int a,int b){
a=findSet(idx,a),b=findSet(idx,b);
if(a==b)return 0;
if(s[a]>s[b])swap(a,b);
p[idx][a]=b,s[idx][b]+=s[idx][a];
return 1;
}
void dfs(int node,int par){
vis[node]=1;G.pb(node);
for(auto it:vec[node]){
if(len)return;
if(it!=par){
if(vis[it]){
len=sz(G);
/*for(auto it:G)
cerr<<it<<" - ";
cerr<<"\n";*/
return;
}
dfs(it,node);
}
}
G.pop_back();
}
void Link(int A, int B) {
if(st)return;
edges.pb({A,B});
vec[A].pb(B),vec[B].pb(A);
deg[0][A]++,deg[0][B]++;
if(flag3)assert(!flag4);
if(flag4)assert(!flag3);
if(!flag3 && !flag4){
bool h=Union(0,A,B);
if(!h && cycle){st=1;return;}
else if(!h){cycle=1;dfs(A,A);}
}
if(flag3){
for (int i = 0; i < 4; ++i){
if(A==pot[i] || B==pot[i])continue;
if(!Union(i+1,A,B))ok[i]=0;
deg[i+1][A]++,deg[i+1][B]++;
if(deg[i+1][A]>=3 || deg[i+1][B]>=3)ok[i]=0;
}
}
else if(k!=A && k!=B && flag4){
if(!Union(5,A,B)){
st=1;return;
}
deg[5][A]++,deg[5][B]++;
if(deg[5][A]>=3 || deg[5][B]>=3){st=1;return;}
}
if(deg[0][A]==3 || deg[0][B]==3){
if(flag3){
bool a=0,b=0;
if(deg[0][A]!=3)a=1;
if(deg[0][B]!=3)b=1;
for (int i = 0; i < 4; ++i)
{
if(pot[i]==A)a=1;
if(pot[i]==B)b=1;
}
if(!a || !b)st=1;
}
else{
flag3=1;
if(deg[0][A]!=3)swap(A,B);
vec[A].pb(A);
for (int i = 0; i < 4; ++i){
bool f=1;
pot[i]=vec[A][i];
for(auto it:edges){
if(it.fi!=vec[A][i] && it.se!=vec[A][i]){
if(!Union(i+1,it.fi,it.se)){f=0;break;}
deg[i+1][it.fi]++,deg[i+1][it.se]++;
if(deg[i+1][it.fi]>=3 || deg[i+1][it.se]>=3){f=0;break;}
}
}
ok[i]=f;
}
vec[A].pop_back();
}
}
else if(deg[0][A]>=4 || deg[0][B]>=4){
if(flag4 || (deg[0][A]>=4 && deg[0][B]>=4))st=1;
else{
flag4=1,flag3=0;
if(deg[0][A]<4)swap(A,B);
k=A;
bool f=1;
for(auto it:edges)
if(it.fi!=A && it.se!=A){
if(!Union(5,it.fi,it.se)){f=0;break;}
deg[5][it.fi]++,deg[5][it.se]++;
if(deg[5][it.fi]>=3 || deg[5][it.se]>=3){f=0;break;}
}
if(!f)st=1;
}
}
}
int CountCritical() {
if(st)return 0;
if(!flag3 && !flag4){
if(!cycle)return N;
else return len;
}
if(flag3)
return ok[0]+ok[1]+ok[2]+ok[3];
if(flag4)return 1;
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
19 ms |
24448 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
24448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
534 ms |
77660 KB |
Output is correct |
| 2 |
Incorrect |
689 ms |
108852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
19 ms |
24448 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
24448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
19 ms |
24448 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
24448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
19 ms |
24448 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
24448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
