#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6 + 5;
static int n;
static vector<int> ciclu;
static vector<int> cen, g3, trk;
static vector<int> vec[nmax + 1];
struct Str {
bool valid;
int grad[nmax + 1], t[nmax + 1];
int g[nmax + 1];
void init () {
valid = 1;
for (int i = 0; i < n; ++ i) {
grad[i] = 1;
t[i] = i;
}
}
inline int find_tata (int x) {
if (x == t[x]) return x;
return t[x] = find_tata(t[x]);
}
void link (int A, int B, int type = -1) {
++ g[A]; ++ g[B];
if (type == 1) {
vec[A].push_back(B);
vec[B].push_back(A);
}
if (valid == 0)
return ;
if (g[A] < 3 && g[B] < 3) {
int la = find_tata(A);
int lb = find_tata(B);
if (la == lb) { // apare ciclu
if (!(type == 1 && (g[A] < 2 && g[B] < 2)))
valid = 0;
} else {
if (grad[la] < grad[lb]) {
swap(la, lb);
swap(A, B);
}
grad[la] += grad[lb];
t[lb] = la;
}
} else
valid = 0;
}
} root, s3[7];
vector<pair<int, int>> e;
int centered;
void Init(int N_) {
n = N_;
centered = -1;
root.init();
}
bool nuexista (int i) {
bool ok = 1;
for (auto j : trk)
if (i == j) ok = 0;
return ok;
}
void invalideaza (int x) {
for (int i = 0; i < trk.size(); ++ i) {
if (trk[i] == x) continue;
bool ok = 0;
for (auto j : vec[x])
if (trk[i] == j)
ok = 1;
if (ok == 0) {
s3[i].valid = 0;
}
}
}
void Link(int A, int B) {
if (root.g[A] == 1 && root.g[B] == 1 && root.find_tata(A) == root.find_tata(B)) {
ciclu.push_back(root.grad[root.find_tata(A)]);
}
e.push_back({A, B});
root.link(A, B, 1);
int old3 = trk.size();
if (cen.size() == 0 && (root.g[A] >= 3 || root.g[B] >= 3)) {
if (g3.size() > 4)
return ;
if (root.g[A] == 3) {
g3.push_back(A);
if (nuexista(A))
trk.push_back(A);
for (auto i : vec[A]) {
if (g3.size() == 1)
trk.push_back(i);
}
invalideaza(A);
}
if (root.g[B] == 3) {
g3.push_back(B);
if (nuexista(B))
trk.push_back(B);
for (auto i : vec[B]) {
if (g3.size() == 1)
trk.push_back(i);
}
invalideaza(B);
}
if (root.g[A] > 3) cen.push_back(A);
if (root.g[B] > 3) cen.push_back(B);
}
if (centered == -1 && cen.size() == 1 && g3.size() <= 4) {
for (int i = 0; i < g3.size(); ++ i) {
if (g3[i] == cen[0])
centered = i;
}
}
// dc nu exista cen, at tin pentru cele 4 g3 uri cum arata fara fiecare
if (cen.size() == 0) {
if (g3.size() > 4)
return ;
for (int i = old3; i < (int)trk.size(); ++ i) {
s3[i].init();
for (auto j : e)
if (j.first != trk[i] && j.second != trk[i])
s3[i].link(j.first, j.second);
}
for (int i = 0; i < old3; ++ i)
if (A != trk[i] && B != trk[i])
s3[i].link(A, B);
}
if (cen.size() == 1)
if (A != cen[0] && B != cen[0])
s3[centered].link(A, B);
}
int CountCritical() {
if (ciclu.size() > 1 || cen.size() > 1) {
return 0;
}
if (g3.size() == 0) {
if (ciclu.size() == 0)
return n;
return ciclu[0];
} else {
if (cen.size() == 0 && g3.size() > 4) // daca sunt 4+ trebuie sa aiba un centru
return 0;
if (cen.size()) {
return s3[centered].valid;
} else {
int cnt = 0;
for (int i = 0; i < (int)trk.size(); ++ i) {
cnt += s3[i].valid;
}
return cnt;
}
}
}
Compilation message
rings.cpp: In function 'void invalideaza(int)':
rings.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < trk.size(); ++ i) {
~~^~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:134:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g3.size(); ++ i) {
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
26 ms |
24448 KB |
Output is correct |
| 3 |
Correct |
29 ms |
24496 KB |
Output is correct |
| 4 |
Correct |
24 ms |
23908 KB |
Output is correct |
| 5 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
28 ms |
24184 KB |
Output is correct |
| 7 |
Correct |
28 ms |
24440 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
24064 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
651 ms |
57312 KB |
Output is correct |
| 2 |
Correct |
1708 ms |
112916 KB |
Output is correct |
| 3 |
Correct |
1446 ms |
153496 KB |
Output is correct |
| 4 |
Correct |
1624 ms |
88116 KB |
Output is correct |
| 5 |
Correct |
1596 ms |
88196 KB |
Output is correct |
| 6 |
Correct |
1482 ms |
86652 KB |
Output is correct |
| 7 |
Correct |
1169 ms |
163780 KB |
Output is correct |
| 8 |
Correct |
2677 ms |
128088 KB |
Output is correct |
| 9 |
Correct |
3427 ms |
146856 KB |
Output is correct |
| 10 |
Incorrect |
1043 ms |
85208 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
26 ms |
24448 KB |
Output is correct |
| 3 |
Correct |
29 ms |
24496 KB |
Output is correct |
| 4 |
Correct |
24 ms |
23908 KB |
Output is correct |
| 5 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
28 ms |
24184 KB |
Output is correct |
| 7 |
Correct |
28 ms |
24440 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
24064 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
26 ms |
24448 KB |
Output is correct |
| 3 |
Correct |
29 ms |
24496 KB |
Output is correct |
| 4 |
Correct |
24 ms |
23908 KB |
Output is correct |
| 5 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
28 ms |
24184 KB |
Output is correct |
| 7 |
Correct |
28 ms |
24440 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
24064 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
26 ms |
24448 KB |
Output is correct |
| 3 |
Correct |
29 ms |
24496 KB |
Output is correct |
| 4 |
Correct |
24 ms |
23908 KB |
Output is correct |
| 5 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
28 ms |
24184 KB |
Output is correct |
| 7 |
Correct |
28 ms |
24440 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
24064 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
