#include <vector>
using namespace std;
int n;
vector<int> edge[1000001];
int phase;
int ans;
void Init(int N) {
n = N;
phase = 0;
ans = n;
}
struct _uf {
int par[1000001];
int sz[1000001];
int st;
int disactive;
_uf() {
for (int i = 1; i <= 1000000; ++i) sz[i] = 1;
}
int find(int x) {
if (par[x]) return par[x] = find(par[x]);
return x;
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x, y);
par[y] = x;
sz[x] += sz[y];
return 1;
}
void disMerge(int x, int y) {
if (!merge(x, y)) disactive = 1;
}
void init(int S) {
st = S;
for (int i = 1; i <= n; ++i) {
if (i == S) continue;
for (int j : edge[i]) {
if (j == S) continue;
if (i < j) disMerge(i, j);
}
}
}
void off(const vector<int> &v) {
if (disactive) return;
for (int i : v) if (st == i) return;
disactive = 1;
}
} uf[5];
void changePhase(int x) {
phase = 1;
uf[1].init(x);
int T = 1;
for (int i : edge[x]) uf[++T].init(i);
}
void checkDeg(int x) {
if (edge[x].size() < 3) return;
vector<int> ch;
ch.push_back(x);
if (edge[x].size() == 3) {
for (int i : edge[x]) ch.push_back(i);
}
int d = 0;
for (int i = 1; i <= 4; ++i) {
uf[i].off(ch);
d += uf[i].disactive;
}
if (d == 4) phase = 2;
}
int cyc = 0;
void Link(int A, int B) {
++A; ++B;
edge[A].push_back(B);
edge[B].push_back(A);
int iniPhase = phase;
if (phase == 0) {
if (edge[A].size() > 2) changePhase(A);
else if (edge[B].size() > 2) changePhase(B);
else {
if (!uf[0].merge(A, B)) {
if (cyc++ == 0) ans = uf[0].sz[uf[0].find(A)];
else phase = 2;
}
}
}
if (phase == 1) checkDeg(A);
if (phase == 1) checkDeg(B);
if (phase == 1 && iniPhase == 1) {
for (int i = 1; i <= 4; ++i) {
if (A == uf[i].st || B == uf[i].st) continue;
uf[i].disMerge(A, B);
}
int d = 0;
for (int i = 1; i <= 4; ++i) d += uf[i].disactive;
if (d == 4) phase = 2;
}
}
int CountCritical() {
if (phase == 0) return ans;
if (phase == 1) {
int ret = 0;
for (int i = 1; i <= 4; ++i) {
if (uf[i].disactive) continue;
++ret;
}
return ret;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
43384 KB |
Output is correct |
2 |
Correct |
38 ms |
43764 KB |
Output is correct |
3 |
Correct |
39 ms |
43764 KB |
Output is correct |
4 |
Correct |
37 ms |
43764 KB |
Output is correct |
5 |
Correct |
40 ms |
43764 KB |
Output is correct |
6 |
Correct |
40 ms |
43940 KB |
Output is correct |
7 |
Correct |
38 ms |
43940 KB |
Output is correct |
8 |
Correct |
39 ms |
43940 KB |
Output is correct |
9 |
Correct |
40 ms |
43940 KB |
Output is correct |
10 |
Correct |
39 ms |
43960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
477 ms |
62164 KB |
Output is correct |
2 |
Correct |
1644 ms |
84448 KB |
Output is correct |
3 |
Correct |
959 ms |
90244 KB |
Output is correct |
4 |
Correct |
1321 ms |
90244 KB |
Output is correct |
5 |
Correct |
1282 ms |
90244 KB |
Output is correct |
6 |
Correct |
1279 ms |
90244 KB |
Output is correct |
7 |
Correct |
937 ms |
90244 KB |
Output is correct |
8 |
Correct |
1888 ms |
91324 KB |
Output is correct |
9 |
Correct |
1983 ms |
94588 KB |
Output is correct |
10 |
Correct |
845 ms |
94588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
43384 KB |
Output is correct |
2 |
Correct |
38 ms |
43764 KB |
Output is correct |
3 |
Correct |
39 ms |
43764 KB |
Output is correct |
4 |
Correct |
37 ms |
43764 KB |
Output is correct |
5 |
Correct |
40 ms |
43764 KB |
Output is correct |
6 |
Correct |
40 ms |
43940 KB |
Output is correct |
7 |
Correct |
38 ms |
43940 KB |
Output is correct |
8 |
Correct |
39 ms |
43940 KB |
Output is correct |
9 |
Correct |
40 ms |
43940 KB |
Output is correct |
10 |
Correct |
39 ms |
43960 KB |
Output is correct |
11 |
Correct |
41 ms |
94588 KB |
Output is correct |
12 |
Correct |
43 ms |
94588 KB |
Output is correct |
13 |
Correct |
43 ms |
94588 KB |
Output is correct |
14 |
Correct |
41 ms |
94588 KB |
Output is correct |
15 |
Correct |
43 ms |
94588 KB |
Output is correct |
16 |
Correct |
43 ms |
94588 KB |
Output is correct |
17 |
Correct |
43 ms |
94588 KB |
Output is correct |
18 |
Correct |
42 ms |
94588 KB |
Output is correct |
19 |
Correct |
41 ms |
94588 KB |
Output is correct |
20 |
Correct |
44 ms |
94588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
43384 KB |
Output is correct |
2 |
Correct |
38 ms |
43764 KB |
Output is correct |
3 |
Correct |
39 ms |
43764 KB |
Output is correct |
4 |
Correct |
37 ms |
43764 KB |
Output is correct |
5 |
Correct |
40 ms |
43764 KB |
Output is correct |
6 |
Correct |
40 ms |
43940 KB |
Output is correct |
7 |
Correct |
38 ms |
43940 KB |
Output is correct |
8 |
Correct |
39 ms |
43940 KB |
Output is correct |
9 |
Correct |
40 ms |
43940 KB |
Output is correct |
10 |
Correct |
39 ms |
43960 KB |
Output is correct |
11 |
Correct |
41 ms |
94588 KB |
Output is correct |
12 |
Correct |
43 ms |
94588 KB |
Output is correct |
13 |
Correct |
43 ms |
94588 KB |
Output is correct |
14 |
Correct |
41 ms |
94588 KB |
Output is correct |
15 |
Correct |
43 ms |
94588 KB |
Output is correct |
16 |
Correct |
43 ms |
94588 KB |
Output is correct |
17 |
Correct |
43 ms |
94588 KB |
Output is correct |
18 |
Correct |
42 ms |
94588 KB |
Output is correct |
19 |
Correct |
41 ms |
94588 KB |
Output is correct |
20 |
Correct |
44 ms |
94588 KB |
Output is correct |
21 |
Correct |
57 ms |
94588 KB |
Output is correct |
22 |
Correct |
69 ms |
94588 KB |
Output is correct |
23 |
Correct |
100 ms |
94588 KB |
Output is correct |
24 |
Correct |
101 ms |
94588 KB |
Output is correct |
25 |
Correct |
69 ms |
94588 KB |
Output is correct |
26 |
Correct |
98 ms |
94588 KB |
Output is correct |
27 |
Correct |
93 ms |
94588 KB |
Output is correct |
28 |
Correct |
88 ms |
94588 KB |
Output is correct |
29 |
Correct |
76 ms |
94588 KB |
Output is correct |
30 |
Correct |
111 ms |
94588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
43384 KB |
Output is correct |
2 |
Correct |
38 ms |
43764 KB |
Output is correct |
3 |
Correct |
39 ms |
43764 KB |
Output is correct |
4 |
Correct |
37 ms |
43764 KB |
Output is correct |
5 |
Correct |
40 ms |
43764 KB |
Output is correct |
6 |
Correct |
40 ms |
43940 KB |
Output is correct |
7 |
Correct |
38 ms |
43940 KB |
Output is correct |
8 |
Correct |
39 ms |
43940 KB |
Output is correct |
9 |
Correct |
40 ms |
43940 KB |
Output is correct |
10 |
Correct |
39 ms |
43960 KB |
Output is correct |
11 |
Correct |
477 ms |
62164 KB |
Output is correct |
12 |
Correct |
1644 ms |
84448 KB |
Output is correct |
13 |
Correct |
959 ms |
90244 KB |
Output is correct |
14 |
Correct |
1321 ms |
90244 KB |
Output is correct |
15 |
Correct |
1282 ms |
90244 KB |
Output is correct |
16 |
Correct |
1279 ms |
90244 KB |
Output is correct |
17 |
Correct |
937 ms |
90244 KB |
Output is correct |
18 |
Correct |
1888 ms |
91324 KB |
Output is correct |
19 |
Correct |
1983 ms |
94588 KB |
Output is correct |
20 |
Correct |
845 ms |
94588 KB |
Output is correct |
21 |
Correct |
41 ms |
94588 KB |
Output is correct |
22 |
Correct |
43 ms |
94588 KB |
Output is correct |
23 |
Correct |
43 ms |
94588 KB |
Output is correct |
24 |
Correct |
41 ms |
94588 KB |
Output is correct |
25 |
Correct |
43 ms |
94588 KB |
Output is correct |
26 |
Correct |
43 ms |
94588 KB |
Output is correct |
27 |
Correct |
43 ms |
94588 KB |
Output is correct |
28 |
Correct |
42 ms |
94588 KB |
Output is correct |
29 |
Correct |
41 ms |
94588 KB |
Output is correct |
30 |
Correct |
44 ms |
94588 KB |
Output is correct |
31 |
Correct |
57 ms |
94588 KB |
Output is correct |
32 |
Correct |
69 ms |
94588 KB |
Output is correct |
33 |
Correct |
100 ms |
94588 KB |
Output is correct |
34 |
Correct |
101 ms |
94588 KB |
Output is correct |
35 |
Correct |
69 ms |
94588 KB |
Output is correct |
36 |
Correct |
98 ms |
94588 KB |
Output is correct |
37 |
Correct |
93 ms |
94588 KB |
Output is correct |
38 |
Correct |
88 ms |
94588 KB |
Output is correct |
39 |
Correct |
76 ms |
94588 KB |
Output is correct |
40 |
Correct |
111 ms |
94588 KB |
Output is correct |
41 |
Correct |
263 ms |
94588 KB |
Output is correct |
42 |
Correct |
800 ms |
94588 KB |
Output is correct |
43 |
Correct |
344 ms |
94588 KB |
Output is correct |
44 |
Correct |
700 ms |
94588 KB |
Output is correct |
45 |
Correct |
843 ms |
94588 KB |
Output is correct |
46 |
Correct |
791 ms |
94588 KB |
Output is correct |
47 |
Correct |
1037 ms |
94588 KB |
Output is correct |
48 |
Correct |
522 ms |
94588 KB |
Output is correct |
49 |
Correct |
814 ms |
94588 KB |
Output is correct |
50 |
Correct |
844 ms |
94588 KB |
Output is correct |
51 |
Correct |
442 ms |
94588 KB |
Output is correct |
52 |
Correct |
621 ms |
94588 KB |
Output is correct |
53 |
Correct |
498 ms |
94588 KB |
Output is correct |
54 |
Correct |
1662 ms |
94588 KB |
Output is correct |
55 |
Correct |
1777 ms |
94588 KB |
Output is correct |