#include <bits/stdc++.h>
using namespace std;
int N;
struct Point{
int parent;
int sz;
};
Point points[1000006];
void construct(int n)
{
for(int i = 0; i <n; i ++)
{
points[i].parent = i;
points[i].sz = 1;
}
}
int find(int u)
{
if(points[u].parent == u) return u;
points[u].parent = find(points[u].parent);
return points[u].parent;
}
void unite(int u, int v)
{
u = find(u);
v = find(v);
if(u !=v)
{
if(points[u].sz > points[v].sz) swap(u, v);
points[u].parent = v;
points[v].sz +=points[u].sz;
}
}
bool stage1 = true, none = false;
int firstcycpar = -1;
vector<int> crit = {};
int cycles = 0;
int deg[1000006];
vector<int> specials;
vector<int>graph[1000006];
bool change = true;
bool valid = false;
bool visited[1000006];
void check_valid(int u, int erd, int par)
{
visited[u] = true;
for(auto v:graph[u])
{
if(v == erd)
{
continue;
}
if(visited[v] && v != par)
{
valid = false; //cout << v << " 1" << '\n';
return;
}
if(!visited[v])
{
int d = 0;
for(auto v1 : graph[v])
{
if (v1 != erd){d ++;}
}
if(d > 2)
{
valid = false; //cout << v << " 2" << '\n';
return;
}
check_valid(v, erd, u);
}
}
}
void Init(int N_)
{
N = N_;
construct(N);
for(int i = 0; i <N; i ++)
{
crit.push_back(i);
}
}
void Link(int A, int B)
{
graph[B].push_back(A);
graph[A].push_back(B);
if(stage1)
{
int a = find(A); int b = find(B);
if( a == b)
{
if(cycles == 1 && a !=firstcycpar)
{
none = true; return;
}
else if(cycles == 0){ cycles ++; firstcycpar = a;}
}
else {unite(a, b);}
a = find(A); b = find(B);
deg[A] ++; deg[B] ++;
if(deg[A] >=3)
{
if(cycles == 1 && firstcycpar!=a)
{
none = true; return;
}
if(cycles == 1 && firstcycpar == a)
stage1 = false;
specials.push_back(A);
for(auto v: graph[A])
{
specials.push_back(v);
}
}
else if(deg[B] >=3)
{
if(cycles == 1 & firstcycpar!=b)
{
none = true; return;
}
stage1 = false;
specials.push_back(B);
for(auto v: graph[B])
{
specials.push_back(v);
}
}
}
else
{
int a = find(A); int b = find(B);
if( a == b)
{
if(cycles == 1 && a!= firstcycpar)
{
none = true; return;
}
else if(cycles == 0 && a != find(specials[0]))
{
none = true; return;
}
else{ cycles ++; firstcycpar = a;}
}
else {unite(a, b);}
deg[A] ++; deg[B] ++;
if(deg[A] == 4 || deg[B] == 4)
{
none = true; return;
}
if(deg[A] == 3)
{
for(int i = 0 ; i <specials.size(); i ++)
{
bool in = false;
for(auto v : graph[A])
{
if(specials[i] == v){in = true;}
}
if(A == specials[i]){in = true;}
if(!in){specials.erase(specials.begin() + i);}
}
}
if(deg[A] == B)
{
for(int i = 0 ; i <specials.size(); i ++)
{
bool in = false;
for(auto v : graph[B])
{
if(specials[i] == v){in = true;}
}
if(B== specials[i]){in = true;}
if(!in){specials.erase(specials.begin() + i);}
}
}
int c = find(specials[0]);
if( a == c || b == c)
{
change = true;
}
}
}
int CountCritical()
{
if(none)
{
return 0;
}
if(stage1)
{
if(cycles == 0)
{
return N;
}
if(cycles == 1)
{
return points[firstcycpar].sz;
}
}
// if there is one of degree 3:
if(change)
{
for(int i = 0; i <specials.size(); i ++)
{
for(int j = 0 ; j <=N; j++)
{
visited[j] = false;
}
valid = true;
//cout << "checking " << specials[i] << '\n';
for(auto x : graph[specials[i]])
{
if(!visited[x])
check_valid(x, specials[i], N);
}
if(!valid)
{
specials.erase(specials.begin() + i);
}
}
change = false;
}
/*
cout << '\n';
for(auto s : specials)
{
cout << s << " ";
}
cout << '\n';
*/
return specials.size();
}
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:126:17: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
126 | if(cycles == 1 & firstcycpar!=b)
| ~~~~~~~^~~~
rings.cpp:163:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i = 0 ; i <specials.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
rings.cpp:176:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(int i = 0 ; i <specials.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:216:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | for(int i = 0; i <specials.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
26968 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
58140 KB |
Output is correct |
| 2 |
Incorrect |
319 ms |
74100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
26968 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
26968 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
26968 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
