# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int MX = 1e6 + 5;
int n, a, b, p[MX], bad_deg[MX],par[4][MX],sz[MX],cnt_cyc = 0,cyc_len = 0, cycles[MX];
int deg_[4][MX], in_deg[MX],can[MX];
vector <int> v[MX], pot;
void Init(int N_) {
n = N_;
for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
}
int get_col(int a) {
if (a == p[a]) return a;
else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
a = get_col(a);
b = get_col(b);
if (a == b) {
cnt_cyc++;
cyc_len = sz[a];
return ;
}
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[b] = a;
sz[b] = 0;
}
int get_col(int a, int ty) {
if (a == par[ty][a]) return a;
else return par[ty][a] = get_col(par[ty][a], ty);
}
void join(int a, int b, int ty) {
// cout<<"join "<<a<<" "<<get_col(a, ty)<<" "<<b<<" "<<get_col(b, ty)<<" "<<ty<<"\n";
deg_[ty][a]++; deg_[ty][b]++;
a = get_col(a, ty);
b = get_col(b, ty);
if (a == b) {
// cout<<"tyy "<<ty<<"\n";
cycles[ty]++;
return ;
}
if(deg_[ty][a] > 2 || deg_[ty][b] > 2) bad_deg[ty] = 1;
par[ty][b] = a;
}
void build(int a, int ty) {
//cout<<"build "<<ty<<" "<<a<<"\n";
for (int i = 1; i <= n; i++) {
par[ty][i] = i;
}
for (int i = 1; i <= n; i++) {
for (int x : v[i]) {
if (i != a && x != a && i < x) join(i, x, ty);
}
}
}
map <int, bool> adj[MX];
void Link(int A, int B) {
A++; B++;
a = A; b = B;
in_deg[a]++; in_deg[b]++;
adj[a][b] = 1; adj[b][a] = 1;
v[a].pb(b); v[b].pb(a);
int ff = 0;
if (in_deg[a] == 4) {
assert(pot.size());
int is_a = 0;
for (int x : pot) if (x == a) is_a = 1;
if (is_a == 0) {
pot.clear(); pot.pb(-1);
return ;
} else {
for (int x : pot) can[x] = 0; can[a] = 1;
}
}
if (in_deg[b] == 4) {
assert(pot.size());
int is_b = 0;
for (int x : pot) if (x == b) is_b = 1;
if (is_b == 0) {
pot.clear(); pot.pb(-1);
return ;
} else {
for (int x : pot) can[x] = 0; can[b] = 1;
}
}
if (in_deg[a] == 3 && !pot.size()) {
pot.pb(a); can[a] = 1; ff = 1;
for (int x : v[a]) pot.pb(x),can[x] = 1;
for (int i = 0; i < pot.size(); i++) build(pot[i], i);
} else if (in_deg[a] == 3 && pot.size()) {
for (int x : pot) {
if (x != a && adj[a][x] != 1) can[x] = 0;
}
}
if (in_deg[b] == 3 && !pot.size()) {
pot.pb(b); can[b] = 1; ff = 1;
for (int x : v[b]) pot.pb(x),can[x] = 1;
for (int i = 0; i < pot.size(); i++) build(pot[i], i);
} else if (in_deg[b] == 3 && pot.size()) {
for (int x : pot) {
if (x != b && adj[b][x] != 1) can[x] = 0;
}
}
col(a, b);
if (pot.size() && pot[0] != -1 ) {
for (int i = 0; i < pot.size(); i++) {
if (a != pot[i] && b != pot[i] && !ff) join(a, b, i);
}
}
}
int CountCritical() {
if (!pot.size()) {
if (cnt_cyc > 1) return 0;
if (cnt_cyc == 0) return n;
if (cnt_cyc == 1) return cyc_len;
}
if (pot.size() && pot[0] == -1) {
return 0;
}
int res = 0;
for (int i = 0; i < pot.size(); i++) {
// cout<<cycles[i]<<" "<<bad_deg[i]<<" "<<can[pot[i]]<<"\n";
if (!can[pot[i]]) continue;
if (!cycles[i] && !bad_deg[i]) res++;
}
return res;
}
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:81:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
81 | for (int x : pot) can[x] = 0; can[a] = 1;
| ^~~
rings.cpp:81:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
81 | for (int x : pot) can[x] = 0; can[a] = 1;
| ^~~
rings.cpp:92:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
92 | for (int x : pot) can[x] = 0; can[b] = 1;
| ^~~
rings.cpp:92:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
92 | for (int x : pot) can[x] = 0; can[b] = 1;
| ^~~
rings.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < pot.size(); i++) build(pot[i], i);
| ~~^~~~~~~~~~~~
rings.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int i = 0; i < pot.size(); i++) build(pot[i], i);
| ~~^~~~~~~~~~~~
rings.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int i = 0; i < pot.size(); i++) {
| ~~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i = 0; i < pot.size(); i++) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70752 KB |
Output is correct |
2 |
Correct |
39 ms |
71612 KB |
Output is correct |
3 |
Correct |
40 ms |
71700 KB |
Output is correct |
4 |
Correct |
35 ms |
70876 KB |
Output is correct |
5 |
Correct |
37 ms |
71120 KB |
Output is correct |
6 |
Correct |
45 ms |
71532 KB |
Output is correct |
7 |
Correct |
38 ms |
71048 KB |
Output is correct |
8 |
Correct |
38 ms |
71316 KB |
Output is correct |
9 |
Correct |
39 ms |
71692 KB |
Output is correct |
10 |
Correct |
42 ms |
71768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
854 ms |
145320 KB |
Output is correct |
2 |
Correct |
2176 ms |
208412 KB |
Output is correct |
3 |
Correct |
1945 ms |
254616 KB |
Output is correct |
4 |
Correct |
1770 ms |
220732 KB |
Output is correct |
5 |
Correct |
1867 ms |
220924 KB |
Output is correct |
6 |
Correct |
1830 ms |
216456 KB |
Output is correct |
7 |
Correct |
1756 ms |
248836 KB |
Output is correct |
8 |
Correct |
2421 ms |
240604 KB |
Output is correct |
9 |
Correct |
2593 ms |
252000 KB |
Output is correct |
10 |
Correct |
1326 ms |
213196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70752 KB |
Output is correct |
2 |
Correct |
39 ms |
71612 KB |
Output is correct |
3 |
Correct |
40 ms |
71700 KB |
Output is correct |
4 |
Correct |
35 ms |
70876 KB |
Output is correct |
5 |
Correct |
37 ms |
71120 KB |
Output is correct |
6 |
Correct |
45 ms |
71532 KB |
Output is correct |
7 |
Correct |
38 ms |
71048 KB |
Output is correct |
8 |
Correct |
38 ms |
71316 KB |
Output is correct |
9 |
Correct |
39 ms |
71692 KB |
Output is correct |
10 |
Correct |
42 ms |
71768 KB |
Output is correct |
11 |
Correct |
51 ms |
71792 KB |
Output is correct |
12 |
Correct |
49 ms |
72608 KB |
Output is correct |
13 |
Correct |
44 ms |
72720 KB |
Output is correct |
14 |
Correct |
42 ms |
72404 KB |
Output is correct |
15 |
Correct |
46 ms |
72840 KB |
Output is correct |
16 |
Correct |
42 ms |
72164 KB |
Output is correct |
17 |
Correct |
44 ms |
72720 KB |
Output is correct |
18 |
Correct |
49 ms |
73232 KB |
Output is correct |
19 |
Correct |
67 ms |
72180 KB |
Output is correct |
20 |
Correct |
44 ms |
72644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70752 KB |
Output is correct |
2 |
Correct |
39 ms |
71612 KB |
Output is correct |
3 |
Correct |
40 ms |
71700 KB |
Output is correct |
4 |
Correct |
35 ms |
70876 KB |
Output is correct |
5 |
Correct |
37 ms |
71120 KB |
Output is correct |
6 |
Correct |
45 ms |
71532 KB |
Output is correct |
7 |
Correct |
38 ms |
71048 KB |
Output is correct |
8 |
Correct |
38 ms |
71316 KB |
Output is correct |
9 |
Correct |
39 ms |
71692 KB |
Output is correct |
10 |
Correct |
42 ms |
71768 KB |
Output is correct |
11 |
Correct |
51 ms |
71792 KB |
Output is correct |
12 |
Correct |
49 ms |
72608 KB |
Output is correct |
13 |
Correct |
44 ms |
72720 KB |
Output is correct |
14 |
Correct |
42 ms |
72404 KB |
Output is correct |
15 |
Correct |
46 ms |
72840 KB |
Output is correct |
16 |
Correct |
42 ms |
72164 KB |
Output is correct |
17 |
Correct |
44 ms |
72720 KB |
Output is correct |
18 |
Correct |
49 ms |
73232 KB |
Output is correct |
19 |
Correct |
67 ms |
72180 KB |
Output is correct |
20 |
Correct |
44 ms |
72644 KB |
Output is correct |
21 |
Correct |
73 ms |
75248 KB |
Output is correct |
22 |
Correct |
78 ms |
77748 KB |
Output is correct |
23 |
Correct |
93 ms |
79660 KB |
Output is correct |
24 |
Correct |
154 ms |
83808 KB |
Output is correct |
25 |
Correct |
63 ms |
76756 KB |
Output is correct |
26 |
Correct |
146 ms |
84088 KB |
Output is correct |
27 |
Correct |
129 ms |
83276 KB |
Output is correct |
28 |
Correct |
137 ms |
87008 KB |
Output is correct |
29 |
Correct |
87 ms |
80220 KB |
Output is correct |
30 |
Correct |
163 ms |
85320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70752 KB |
Output is correct |
2 |
Correct |
39 ms |
71612 KB |
Output is correct |
3 |
Correct |
40 ms |
71700 KB |
Output is correct |
4 |
Correct |
35 ms |
70876 KB |
Output is correct |
5 |
Correct |
37 ms |
71120 KB |
Output is correct |
6 |
Correct |
45 ms |
71532 KB |
Output is correct |
7 |
Correct |
38 ms |
71048 KB |
Output is correct |
8 |
Correct |
38 ms |
71316 KB |
Output is correct |
9 |
Correct |
39 ms |
71692 KB |
Output is correct |
10 |
Correct |
42 ms |
71768 KB |
Output is correct |
11 |
Correct |
854 ms |
145320 KB |
Output is correct |
12 |
Correct |
2176 ms |
208412 KB |
Output is correct |
13 |
Correct |
1945 ms |
254616 KB |
Output is correct |
14 |
Correct |
1770 ms |
220732 KB |
Output is correct |
15 |
Correct |
1867 ms |
220924 KB |
Output is correct |
16 |
Correct |
1830 ms |
216456 KB |
Output is correct |
17 |
Correct |
1756 ms |
248836 KB |
Output is correct |
18 |
Correct |
2421 ms |
240604 KB |
Output is correct |
19 |
Correct |
2593 ms |
252000 KB |
Output is correct |
20 |
Correct |
1326 ms |
213196 KB |
Output is correct |
21 |
Correct |
51 ms |
71792 KB |
Output is correct |
22 |
Correct |
49 ms |
72608 KB |
Output is correct |
23 |
Correct |
44 ms |
72720 KB |
Output is correct |
24 |
Correct |
42 ms |
72404 KB |
Output is correct |
25 |
Correct |
46 ms |
72840 KB |
Output is correct |
26 |
Correct |
42 ms |
72164 KB |
Output is correct |
27 |
Correct |
44 ms |
72720 KB |
Output is correct |
28 |
Correct |
49 ms |
73232 KB |
Output is correct |
29 |
Correct |
67 ms |
72180 KB |
Output is correct |
30 |
Correct |
44 ms |
72644 KB |
Output is correct |
31 |
Correct |
73 ms |
75248 KB |
Output is correct |
32 |
Correct |
78 ms |
77748 KB |
Output is correct |
33 |
Correct |
93 ms |
79660 KB |
Output is correct |
34 |
Correct |
154 ms |
83808 KB |
Output is correct |
35 |
Correct |
63 ms |
76756 KB |
Output is correct |
36 |
Correct |
146 ms |
84088 KB |
Output is correct |
37 |
Correct |
129 ms |
83276 KB |
Output is correct |
38 |
Correct |
137 ms |
87008 KB |
Output is correct |
39 |
Correct |
87 ms |
80220 KB |
Output is correct |
40 |
Correct |
163 ms |
85320 KB |
Output is correct |
41 |
Correct |
351 ms |
107432 KB |
Output is correct |
42 |
Correct |
1104 ms |
170584 KB |
Output is correct |
43 |
Correct |
378 ms |
124620 KB |
Output is correct |
44 |
Correct |
1363 ms |
234140 KB |
Output is correct |
45 |
Correct |
1265 ms |
206048 KB |
Output is correct |
46 |
Correct |
1270 ms |
194724 KB |
Output is correct |
47 |
Correct |
1577 ms |
197080 KB |
Output is correct |
48 |
Correct |
800 ms |
168584 KB |
Output is correct |
49 |
Correct |
1186 ms |
184456 KB |
Output is correct |
50 |
Correct |
1228 ms |
184068 KB |
Output is correct |
51 |
Correct |
519 ms |
125960 KB |
Output is correct |
52 |
Correct |
1446 ms |
203572 KB |
Output is correct |
53 |
Correct |
858 ms |
172084 KB |
Output is correct |
54 |
Correct |
2234 ms |
217212 KB |
Output is correct |
55 |
Correct |
2348 ms |
230972 KB |
Output is correct |