#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
const int Nn = 1e6 + 6;
bool cycle, us[Nn];
int n, p[Nn], sz[Nn], pr[Nn], cr[Nn];
vector < int > v[Nn];
set < int > ans;
int P(int x) {
if (p[x] == x) return x;
return p[x] = P(p[x]);
}
void Init(int N_) {
n = N_;
for (int i = 0; i < n; ++i) {
ans.insert(i);
p[i] = i;
}
}
void intr(set < int > cur) {
int crs = 0;
for (set < int > :: iterator it = cur.begin(); it != cur.end(); ++it) {
if (ans.find(*it) == ans.end()) continue;
cr[++crs] = (*it);
}
ans.clear();
for (int i = 1; i <= crs; ++i) {
ans.insert(cr[i]);
}
}
vector < int > rec;
void dfs(int x, int p, int fn) {
pr[x] = p;
us[x] = true;
rec.pb(x);
if (x == fn) {
set < int > cur;
cur.insert(x);
x = pr[x];
cycle = true;
while (x != fn) {
cur.insert(x);
x = pr[x];
}
intr(cur);
return ;
}
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
if (to != p && !us[to]) dfs(to, x, fn);
if (cycle) return ;
}
}
void Link(int A, int B) {
int ap = P(A), bp = P(B);
v[A].pb(B), v[B].pb(A);
if (ap != bp) {
if (sz[ap] < sz[bp]) swap(ap, bp);
sz[ap] += sz[bp];
p[bp] = ap;
}
else {
++sz[ap];
if (sz[ap] <= 3) {
cycle = false;
dfs(A, B, B);
}
for (int i = 0; i < rec.size(); ++i) {
us[rec[i]] = false;
}
rec.clear();
if (sz[ap] == 2) {
set < int > cur;
int crs = 0;
for (set < int > :: iterator it = ans.begin(); it != ans.end(); ++it) {
if (v[(*it)].size() >= 3) {
cr[++crs] = (*it);
}
}
ans.clear();
for (int i = 1; i <= crs; ++i) {
ans.insert(cr[i]);
}
}
}
set < int > st;
if (v[A].size() == 4) st.clear(), st.insert(A), intr(st);
if (v[B].size() == 4) st.clear(), st.insert(B), intr(st);
if (v[A].size() == 3) st.clear(), st.insert(A), st.insert(v[A][0]), st.insert(v[A][1]), st.insert(v[A][2]), intr(st);
if (v[B].size() == 3) st.clear(), st.insert(B), st.insert(v[B][0]), st.insert(v[B][1]), st.insert(v[B][2]), intr(st);
}
int CountCritical() {
return ans.size();
}
Compilation message
rings.cpp: In function 'void dfs(int, int, int)':
rings.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < rec.size(); ++i) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23888 KB |
Output is correct |
2 |
Correct |
15 ms |
24148 KB |
Output is correct |
3 |
Correct |
14 ms |
24200 KB |
Output is correct |
4 |
Correct |
12 ms |
23892 KB |
Output is correct |
5 |
Correct |
13 ms |
24592 KB |
Output is correct |
6 |
Correct |
16 ms |
25280 KB |
Output is correct |
7 |
Correct |
13 ms |
24080 KB |
Output is correct |
8 |
Correct |
14 ms |
24416 KB |
Output is correct |
9 |
Correct |
16 ms |
24276 KB |
Output is correct |
10 |
Correct |
14 ms |
24452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
72004 KB |
Output is correct |
2 |
Correct |
885 ms |
90288 KB |
Output is correct |
3 |
Correct |
1147 ms |
96852 KB |
Output is correct |
4 |
Correct |
1123 ms |
125924 KB |
Output is correct |
5 |
Correct |
1131 ms |
133888 KB |
Output is correct |
6 |
Correct |
1837 ms |
262144 KB |
Output is correct |
7 |
Correct |
1122 ms |
96352 KB |
Output is correct |
8 |
Correct |
1068 ms |
114024 KB |
Output is correct |
9 |
Correct |
1111 ms |
122336 KB |
Output is correct |
10 |
Correct |
1523 ms |
140692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23888 KB |
Output is correct |
2 |
Correct |
15 ms |
24148 KB |
Output is correct |
3 |
Correct |
14 ms |
24200 KB |
Output is correct |
4 |
Correct |
12 ms |
23892 KB |
Output is correct |
5 |
Correct |
13 ms |
24592 KB |
Output is correct |
6 |
Correct |
16 ms |
25280 KB |
Output is correct |
7 |
Correct |
13 ms |
24080 KB |
Output is correct |
8 |
Correct |
14 ms |
24416 KB |
Output is correct |
9 |
Correct |
16 ms |
24276 KB |
Output is correct |
10 |
Correct |
14 ms |
24452 KB |
Output is correct |
11 |
Correct |
13 ms |
24276 KB |
Output is correct |
12 |
Correct |
17 ms |
25028 KB |
Output is correct |
13 |
Correct |
17 ms |
24912 KB |
Output is correct |
14 |
Correct |
16 ms |
24464 KB |
Output is correct |
15 |
Correct |
19 ms |
25148 KB |
Output is correct |
16 |
Correct |
19 ms |
24860 KB |
Output is correct |
17 |
Correct |
18 ms |
24700 KB |
Output is correct |
18 |
Correct |
19 ms |
25172 KB |
Output is correct |
19 |
Correct |
17 ms |
24968 KB |
Output is correct |
20 |
Correct |
16 ms |
24776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23888 KB |
Output is correct |
2 |
Correct |
15 ms |
24148 KB |
Output is correct |
3 |
Correct |
14 ms |
24200 KB |
Output is correct |
4 |
Correct |
12 ms |
23892 KB |
Output is correct |
5 |
Correct |
13 ms |
24592 KB |
Output is correct |
6 |
Correct |
16 ms |
25280 KB |
Output is correct |
7 |
Correct |
13 ms |
24080 KB |
Output is correct |
8 |
Correct |
14 ms |
24416 KB |
Output is correct |
9 |
Correct |
16 ms |
24276 KB |
Output is correct |
10 |
Correct |
14 ms |
24452 KB |
Output is correct |
11 |
Correct |
13 ms |
24276 KB |
Output is correct |
12 |
Correct |
17 ms |
25028 KB |
Output is correct |
13 |
Correct |
17 ms |
24912 KB |
Output is correct |
14 |
Correct |
16 ms |
24464 KB |
Output is correct |
15 |
Correct |
19 ms |
25148 KB |
Output is correct |
16 |
Correct |
19 ms |
24860 KB |
Output is correct |
17 |
Correct |
18 ms |
24700 KB |
Output is correct |
18 |
Correct |
19 ms |
25172 KB |
Output is correct |
19 |
Correct |
17 ms |
24968 KB |
Output is correct |
20 |
Correct |
16 ms |
24776 KB |
Output is correct |
21 |
Correct |
33 ms |
27980 KB |
Output is correct |
22 |
Correct |
50 ms |
30404 KB |
Output is correct |
23 |
Correct |
66 ms |
32028 KB |
Output is correct |
24 |
Correct |
73 ms |
30284 KB |
Output is correct |
25 |
Correct |
45 ms |
29712 KB |
Output is correct |
26 |
Correct |
57 ms |
30624 KB |
Output is correct |
27 |
Correct |
80 ms |
32036 KB |
Output is correct |
28 |
Correct |
63 ms |
30328 KB |
Output is correct |
29 |
Correct |
73 ms |
30232 KB |
Output is correct |
30 |
Correct |
95 ms |
37436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23888 KB |
Output is correct |
2 |
Correct |
15 ms |
24148 KB |
Output is correct |
3 |
Correct |
14 ms |
24200 KB |
Output is correct |
4 |
Correct |
12 ms |
23892 KB |
Output is correct |
5 |
Correct |
13 ms |
24592 KB |
Output is correct |
6 |
Correct |
16 ms |
25280 KB |
Output is correct |
7 |
Correct |
13 ms |
24080 KB |
Output is correct |
8 |
Correct |
14 ms |
24416 KB |
Output is correct |
9 |
Correct |
16 ms |
24276 KB |
Output is correct |
10 |
Correct |
14 ms |
24452 KB |
Output is correct |
11 |
Correct |
441 ms |
72004 KB |
Output is correct |
12 |
Correct |
885 ms |
90288 KB |
Output is correct |
13 |
Correct |
1147 ms |
96852 KB |
Output is correct |
14 |
Correct |
1123 ms |
125924 KB |
Output is correct |
15 |
Correct |
1131 ms |
133888 KB |
Output is correct |
16 |
Correct |
1837 ms |
262144 KB |
Output is correct |
17 |
Correct |
1122 ms |
96352 KB |
Output is correct |
18 |
Correct |
1068 ms |
114024 KB |
Output is correct |
19 |
Correct |
1111 ms |
122336 KB |
Output is correct |
20 |
Correct |
1523 ms |
140692 KB |
Output is correct |
21 |
Correct |
13 ms |
24276 KB |
Output is correct |
22 |
Correct |
17 ms |
25028 KB |
Output is correct |
23 |
Correct |
17 ms |
24912 KB |
Output is correct |
24 |
Correct |
16 ms |
24464 KB |
Output is correct |
25 |
Correct |
19 ms |
25148 KB |
Output is correct |
26 |
Correct |
19 ms |
24860 KB |
Output is correct |
27 |
Correct |
18 ms |
24700 KB |
Output is correct |
28 |
Correct |
19 ms |
25172 KB |
Output is correct |
29 |
Correct |
17 ms |
24968 KB |
Output is correct |
30 |
Correct |
16 ms |
24776 KB |
Output is correct |
31 |
Correct |
33 ms |
27980 KB |
Output is correct |
32 |
Correct |
50 ms |
30404 KB |
Output is correct |
33 |
Correct |
66 ms |
32028 KB |
Output is correct |
34 |
Correct |
73 ms |
30284 KB |
Output is correct |
35 |
Correct |
45 ms |
29712 KB |
Output is correct |
36 |
Correct |
57 ms |
30624 KB |
Output is correct |
37 |
Correct |
80 ms |
32036 KB |
Output is correct |
38 |
Correct |
63 ms |
30328 KB |
Output is correct |
39 |
Correct |
73 ms |
30232 KB |
Output is correct |
40 |
Correct |
95 ms |
37436 KB |
Output is correct |
41 |
Correct |
282 ms |
63228 KB |
Output is correct |
42 |
Correct |
571 ms |
89172 KB |
Output is correct |
43 |
Correct |
437 ms |
83308 KB |
Output is correct |
44 |
Correct |
793 ms |
91420 KB |
Output is correct |
45 |
Correct |
941 ms |
107008 KB |
Output is correct |
46 |
Correct |
1143 ms |
110128 KB |
Output is correct |
47 |
Correct |
1334 ms |
195760 KB |
Output is correct |
48 |
Correct |
664 ms |
87228 KB |
Output is correct |
49 |
Correct |
772 ms |
114600 KB |
Output is correct |
50 |
Correct |
814 ms |
113328 KB |
Output is correct |
51 |
Correct |
448 ms |
75544 KB |
Output is correct |
52 |
Correct |
698 ms |
78852 KB |
Output is correct |
53 |
Correct |
654 ms |
86080 KB |
Output is correct |
54 |
Correct |
926 ms |
98552 KB |
Output is correct |
55 |
Correct |
974 ms |
84740 KB |
Output is correct |