#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int Ni = 1e6+5;
vector<int> edges[Ni];
int n, ans;
// start of DSU
vector<int> p;
vector<int> sz;
vector<int> cyclic;
int par(int u){
if(p[u] == u)return u;
return p[u] = par(p[u]);
}
bool IsSame(int u, int v){
return par(u) == par(v);
}
void merge(int u,int v){
u=par(u);v=par(v);
if(u == v)return;
p[v] = u;
sz[u] += sz[v];
cyclic[u] |= cyclic[v];
return;
}
int size_of_node(int u){
return sz[par(u)];
}// end of DSU
int have_this_number_of_edges[5];
void Init(int N_) {
n = N_;
ans = n;
p.assign(n,0);
sz.assign(n,0);
cyclic.assign(n,0);
for(int i=0;i<n;i++)p[i] = i;
have_this_number_of_edges[0] = n;
}
int number_of_cycles;
void del(int u){
have_this_number_of_edges[min(4,(int)edges[u].size())]--;
}void add(int u){
have_this_number_of_edges[min(4,(int)edges[u].size())]++;
}
void Link(int u, int v){
del(u);del(v);
edges[u].pb(v);
edges[v].pb(u);
add(u);add(v);
if(IsSame(u, v)){
number_of_cycles++;
cyclic[par(u)] = 1;
}else {
merge(u,v);
}return;
}
int please_dont_go_there;
bool is_it_normal;
bool used[Ni];
void dfs(int u, int p){
used[u] = true;
int cnt= 0 ;
for(auto v : edges[u]){
if(v != please_dont_go_there)cnt++;
if(v == p || v == please_dont_go_there)continue;
if(used[v])is_it_normal = false;
else dfs(v,u);
}if(cnt>2)is_it_normal = false;
}
bool CheckItPlease(int to_delete){
please_dont_go_there = to_delete;
for(int j=0;j<n;j++)used[j] = false;
used[please_dont_go_there] = true;
is_it_normal = true;
for(int j=0;j<n;j++){
if(!used[j])dfs(j,j);
}return is_it_normal;
}
bool is_it_in_cycle[Ni];
int parent[Ni];
void PleaseFindCycles(int u, int p){
parent[u] = p;
used[u] = true;
for(auto v : edges[u]){
if(v == p)continue;
if(used[v]){
int x = u;
while(x != v){
cout << x << ' ';
is_it_in_cycle[x]=1;
x=parent[x];
}is_it_in_cycle[x]=1;
}else {
PleaseFindCycles(v,u);
}
}
}
int CountCritical(){
if(have_this_number_of_edges[4] > 1)return 0;
if(!number_of_cycles && have_this_number_of_edges[3]+have_this_number_of_edges[4]==0)return n;
ans = 0;
for(int i=0;i<n;i++){
used[i] = is_it_in_cycle[i] = false;
} if(have_this_number_of_edges[4] == 1){
int we_need_it;
for(int i=0;i<n;i++){
if(edges[i].size() >= 4){
we_need_it = i;break;
}
}
ans += CheckItPlease(we_need_it);
}else if(have_this_number_of_edges[3] > 0){
int we_need_it;
for(int i=0;i<n;i++){
if(edges[i].size() == 3){
we_need_it = i;break;
}
}
ans += CheckItPlease(we_need_it);
for(auto v : edges[we_need_it])ans += CheckItPlease(v);
}else if(have_this_number_of_edges[2] > 0){
//~ for(int i=0;i<n;i++){
//~ if(!used[i]){
//~ PleaseFindCycles(i,i);
//~ }
//~ }
if(number_of_cycles > 1)return 0;
for(int i=0;i<n;i++){
if(cyclic[par(i)])ans = max(ans, size_of_node(i));
}return ans;
}else assert(false);
return ans;
}
Compilation message
rings.cpp: In function 'int CountCritical()':
rings.cpp:124:7: warning: 'we_need_it' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | int we_need_it;
| ^~~~~~~~~~
rings.cpp:122:23: warning: 'we_need_it' may be used uninitialized in this function [-Wmaybe-uninitialized]
122 | ans += CheckItPlease(we_need_it);
| ~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
482 ms |
46188 KB |
Output is correct |
| 2 |
Correct |
1164 ms |
60268 KB |
Output is correct |
| 3 |
Correct |
1237 ms |
62956 KB |
Output is correct |
| 4 |
Incorrect |
1190 ms |
68972 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
