#ifndef EVAL
#include"grader.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
vector<int>g[1000005];
bool on[1000005],vis[1000005];
int n,deg[1000005];
int counter[6];
bool flag;
int cycle_number,cycle_size;
int update_counter(int x,int y){
x=min(x,5);
counter[x]+=y;
}
void go(int v,int p){
vis[v]=1;
for(int to:g[v])if(to!=p){
if(vis[to]){
flag=true;
continue;
}
go(to,v);
}
}
bool dfs(int v,int p){
bool flag=false;
vis[v]=true;
for(int to:g[v])if(to!=p){
if(on[to])continue;
if(flag)return false;
if(vis[to])return false;
if(!dfs(to,v))return false;
flag=true;
}
return true;
}
bool check(){
for(int i=0;i<n;i++)vis[i]=0;
for(int i=0;i<n;i++)if(!on[i]&&!vis[i]&°[i]<2)if(!dfs(i,i))return false;
for(int i=0;i<n;i++)if(!vis[i]&&!on[i])return false;
return true;
}
void Init(int N){
n=N;
counter[0]=n;
}
void Link(int x,int y){
g[x].push_back(y);
g[y].push_back(x);
update_counter(deg[x],-1);
update_counter(deg[y],-1);
deg[x]++;
deg[y]++;
update_counter(deg[x],+1);
update_counter(deg[y],+1);
}
int CountCritical(){
if(counter[4]||counter[5]){
if(counter[4]+counter[5]!=1)return 0;
int cnt=0;
for(int i=0;i<n;i++){
if(deg[i]>3){
on[i]=true;
for(auto to:g[i])deg[to]--;
cnt+=check();
for(auto to:g[i])deg[to]++;
on[i]=false;
}
}
return cnt;
}else if(counter[3]){
for(int i=0;i<n;i++){
int cnt=0;
if(deg[i]==3){
on[i]=true;
for(auto to:g[i])deg[to]--;
cnt+=check();
for(auto to:g[i])deg[to]++;
on[i]=false;
for(int to:g[i]){
on[to]=true;
for(auto to2:g[to])deg[to2]--;
cnt+=check();
for(auto to2:g[to])deg[to2]++;
on[to]=false;
}
return cnt;
}
}
}else if(counter[2]){
for(int i=0;i<n;i++)vis[i]=0;
cycle_number=0,cycle_size=0;
for(int i=0;i<n;i++)
if(!vis[i]){
flag=false;
go(i,i);
if(flag)cycle_number++;
else if(!cycle_number)cycle_size=0;
}
if(cycle_number==0)return n;
else if(cycle_number==1)return cycle_size;
else return 0;
}else if(counter[0]||counter[1])return n;
}
/*
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 'int update_counter(int, int)':
rings.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
15 | }
| ^
rings.cpp: In function 'int CountCritical()':
rings.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
105 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
48236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
48364 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
48236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
48236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
48236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
