#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
const int Nn = 1e6 + 6;
bool cycle, new_cycle = false, REKT, f[Nn], us[Nn], in_cycle[Nn];
int n, ans, CM = -1, degreemax, len, comp, p[Nn], sz[Nn], pr[Nn];
set < pair < int , int > > st;
vector < int > v[Nn];
int P(int x) {
if (p[x] == x) return x;
return p[x] = P(p[x]);
}
void Init(int N_) {
n = ans = N_;
degreemax = 0;
for (int i = 0; i < n; ++i) {
st.insert({v[i].size(), i});
p[i] = i;
}
}
void dfs(int x, int p, int fn) {
pr[x] = p;
if (x == fn) {
len = 1;
cycle = true;
in_cycle[x] = true;
cout << "start cycle\n";
cout << x << "in cycle \n";
while (x != pr[x]) {
++len;
x = pr[x];
cout << x << " in cycle \n";
in_cycle[x] = true;
}
cout << "END CYCLE\n";
return ;
}
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
if (to != p) dfs(to, x, fn);
if (cycle) return ;
}
}
bool okr;
void wfs(int x, int p, int fn) {
pr[x] = p;
if (in_cycle[x]) {
if (CM == -1) CM = x;
else
if (CM != x) REKT = true;
else
if (CM == x) okr = true;
}
if (x == fn) {
new_cycle = true;
in_cycle[x] = true;
while (x != pr[x]) {
x = pr[x];
in_cycle[x] = true;
}
return ;
}
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
if (to != p) wfs(to, x, fn);
if (new_cycle || REKT) return ;
}
}
void Link(int A, int B) {
int ap = P(A), bp = P(B);
if (ap != bp) {
if (sz[ap] < sz[bp]) swap(ap, bp);
sz[ap] += sz[bp];
p[bp] = ap;
}
else {
if (!cycle) {
//comp = A;
dfs(A, A, B);
assert(cycle == true);
}
else
if (cycle) {
if (!REKT) {
new_cycle = false;
if (CM == -1) {
wfs(A, A, B);
if (CM == -1) {
REKT = true;
}
}
else {
okr = false;
wfs(A, A, B);
if (!okr) {
REKT = true;
}
}
}
}
}
st.erase(st.find({v[A].size(), A}));
st.erase(st.find({v[B].size(), B}));
v[A].pb(B), v[B].pb(A);
st.insert({v[A].size(), A});
st.insert({v[B].size(), B});
if (v[A].size() > v[degreemax].size()) degreemax = A;
if (v[B].size() > v[degreemax].size()) degreemax = B;
}
bool check(int x) {
if (cycle && (CM == -1 && !in_cycle[x])) return 0;
if (CM != -1 && CM != x) return 0;
st.erase(st.find({v[x].size(), x}));
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
st.erase(st.find({v[to].size(), to}));
st.insert({v[to].size() - 1, to});
}
bool ok = true;
if (st.size() && (*st.rbegin()).f > 2) ok = false;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
st.erase(st.find({v[to].size() - 1, to}));
st.insert({v[to].size(), to});
}
st.insert({v[x].size(), x});
return ok;
}
int CountCritical() {
if (REKT) return 0;
if (v[degreemax].size() <= 2) {
if (!cycle) return n;
return len;
}
int res = 0;
for (int i = 0; i < n; ++i) {
res += check(i);
}
return res;
/*
if (v[degreemax].size() > 3) {
if (cycle && !in_cycle[degreemax]) return 0;
st.erase(st.find({v[degreemax].size(), degreemax}));
if ((*st.rbegin()).f > 3) return 0;
st.insert({v[degreemax].size(), degreemax});
for (int i = 0; i < v[degreemax].size(); ++i) {
us[v[degreemax][i]] = true;
}
bool ok = true;
for (int i = 0; i < n; ++i) {
if (i != degreemax && !us[i] && v[i].size() > 2) {
ok = false;
break;
}
}
for (int i = 0; i < v[degreemax].size(); ++i) {
us[v[degreemax][i]] = false;
}
return ok;
}
if (v[degreemax].size() == 3) {
int res = 0;
res += check(degreemax);
res += check(v[degreemax][0]);
res += check(v[degreemax][1]);
res += check(v[degreemax][2]);
return res;
}*/
}
Compilation message
rings.cpp: In function 'void dfs(int, int, int)':
rings.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
rings.cpp: In function 'void wfs(int, int, int)':
rings.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
rings.cpp: In function 'bool check(int)':
rings.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
rings.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24148 KB |
Output is correct |
| 3 |
Correct |
32 ms |
24284 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1857 ms |
68668 KB |
Output is correct |
| 2 |
Execution timed out |
4017 ms |
95608 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24148 KB |
Output is correct |
| 3 |
Correct |
32 ms |
24284 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24148 KB |
Output is correct |
| 3 |
Correct |
32 ms |
24284 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24148 KB |
Output is correct |
| 3 |
Correct |
32 ms |
24284 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
