#include "bits/stdc++.h"
using namespace std;
int N;
struct dsu {
bool cycle[1000010];
int head[1000010];
int tail[1000010];
int par[1000010];
int len[1000010];
int cycle_cnt;
int cycle_sum;
bool bad;
int no_of_nodes;
int del_node;
void init (int n) {
no_of_nodes = n;
del_node = -1;
for(int i = 0; i < no_of_nodes; i++) {
cycle[i] = false;
head[i] = tail[i] = par[i] = i;
len[i] = 1;
}
cycle_cnt = 0;
cycle_sum = 0;
bad = false;
}
int root(int x) {
if(x == par[x]) return par[x];
return par[x] = root(par[x]);
}
void add(int x, int y) {
if(del_node == x || del_node == y) return ;
if(bad) return ;
int p = root(x);
int q = root(y);
if(p == q) {
if(cycle[p]) {
bad = true;
return ;
} else if(head[p] == x && tail[p] == y) {
cycle_cnt += 1;
cycle_sum += len[p];
cycle[p] = true;
} else if (head[p] == y && tail[p] == x) {
cycle_cnt += 1;
cycle_sum += len[p];
cycle[p] = true;
} else {
bad = true;
return ;
}
} else {
if(cycle[p] || cycle[q]) {
bad = true;
return ;
}
par[p] = q;
len[q] += len[p];
if(x == head[p]) {
if(y == head[q]) {
head[q] = tail[p];
} else if (y == tail[q]) {
tail[q] = tail[p];
} else {
bad = true;
return ;
}
} else if (x == tail[p]) {
if(y == head[q]) {
head[q] = head[p];
} else if (y == tail[q]) {
tail[q] = head[p];
} else {
bad = true;
return ;
}
} else {
bad = true;
return ;
}
}
}
int count() {
if(bad) return 0;
if(cycle_cnt <= 1) {
if(cycle_cnt == 1) return cycle_sum;
else return no_of_nodes;
}
return 0;
}
} T[5];
vector <int> g[1000010];
vector <int> l, r;
bool found_cand;
void Init(int N_) {
N = N_;
for(int i = 0; i < 5; i++) {
T[i].init(N);
}
for(int i = 0; i < N; i++) {
g[i].clear();
}
l.clear(); r.clear();
found_cand = false;
}
void Link(int A, int B) {
if(found_cand) {
for(int i = 1; i <= 4; i++) {
T[i].add(A, B);
}
return ;
}
l.emplace_back(A);
r.emplace_back(B);
g[A].emplace_back(B);
g[B].emplace_back(A);
if(g[A].size() == 3) {
T[1].del_node = A;
T[2].del_node = g[A][0];
T[3].del_node = g[A][1];
T[4].del_node = g[A][2];
found_cand = true;
} else if (g[B].size() == 3) {
T[1].del_node = B;
T[2].del_node = g[B][0];
T[3].del_node = g[B][1];
T[4].del_node = g[B][2];
found_cand = true;
} else {
T[0].add(A, B);
}
if(found_cand) {
for(int i = 0; i < (int)l.size(); i++) {
Link(l[i], r[i]);
}
}
}
int CountCritical() {
if(found_cand) {
int ans = 0;
for(int i = 1; i <= 4; i++) {
if(T[i].cycle_cnt == 0 && !T[i].bad) {
++ans;
}
}
return ans;
}
return T[0].count();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24548 KB |
Output is correct |
3 |
Correct |
23 ms |
24548 KB |
Output is correct |
4 |
Correct |
22 ms |
24548 KB |
Output is correct |
5 |
Correct |
23 ms |
24548 KB |
Output is correct |
6 |
Correct |
26 ms |
24856 KB |
Output is correct |
7 |
Correct |
22 ms |
24856 KB |
Output is correct |
8 |
Correct |
25 ms |
24856 KB |
Output is correct |
9 |
Correct |
24 ms |
24856 KB |
Output is correct |
10 |
Correct |
25 ms |
24856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
578 ms |
87884 KB |
Output is correct |
2 |
Correct |
1377 ms |
107552 KB |
Output is correct |
3 |
Correct |
459 ms |
107832 KB |
Output is correct |
4 |
Correct |
1589 ms |
146468 KB |
Output is correct |
5 |
Correct |
1560 ms |
146500 KB |
Output is correct |
6 |
Correct |
1529 ms |
146500 KB |
Output is correct |
7 |
Correct |
413 ms |
146500 KB |
Output is correct |
8 |
Correct |
3268 ms |
146500 KB |
Output is correct |
9 |
Correct |
3944 ms |
146500 KB |
Output is correct |
10 |
Correct |
1109 ms |
146500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24548 KB |
Output is correct |
3 |
Correct |
23 ms |
24548 KB |
Output is correct |
4 |
Correct |
22 ms |
24548 KB |
Output is correct |
5 |
Correct |
23 ms |
24548 KB |
Output is correct |
6 |
Correct |
26 ms |
24856 KB |
Output is correct |
7 |
Correct |
22 ms |
24856 KB |
Output is correct |
8 |
Correct |
25 ms |
24856 KB |
Output is correct |
9 |
Correct |
24 ms |
24856 KB |
Output is correct |
10 |
Correct |
25 ms |
24856 KB |
Output is correct |
11 |
Correct |
25 ms |
146500 KB |
Output is correct |
12 |
Correct |
28 ms |
146500 KB |
Output is correct |
13 |
Correct |
28 ms |
146500 KB |
Output is correct |
14 |
Correct |
27 ms |
146500 KB |
Output is correct |
15 |
Correct |
26 ms |
146500 KB |
Output is correct |
16 |
Correct |
33 ms |
146500 KB |
Output is correct |
17 |
Correct |
26 ms |
146500 KB |
Output is correct |
18 |
Correct |
32 ms |
146500 KB |
Output is correct |
19 |
Correct |
29 ms |
146500 KB |
Output is correct |
20 |
Correct |
28 ms |
146500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24548 KB |
Output is correct |
3 |
Correct |
23 ms |
24548 KB |
Output is correct |
4 |
Correct |
22 ms |
24548 KB |
Output is correct |
5 |
Correct |
23 ms |
24548 KB |
Output is correct |
6 |
Correct |
26 ms |
24856 KB |
Output is correct |
7 |
Correct |
22 ms |
24856 KB |
Output is correct |
8 |
Correct |
25 ms |
24856 KB |
Output is correct |
9 |
Correct |
24 ms |
24856 KB |
Output is correct |
10 |
Correct |
25 ms |
24856 KB |
Output is correct |
11 |
Correct |
25 ms |
146500 KB |
Output is correct |
12 |
Correct |
28 ms |
146500 KB |
Output is correct |
13 |
Correct |
28 ms |
146500 KB |
Output is correct |
14 |
Correct |
27 ms |
146500 KB |
Output is correct |
15 |
Correct |
26 ms |
146500 KB |
Output is correct |
16 |
Correct |
33 ms |
146500 KB |
Output is correct |
17 |
Correct |
26 ms |
146500 KB |
Output is correct |
18 |
Correct |
32 ms |
146500 KB |
Output is correct |
19 |
Correct |
29 ms |
146500 KB |
Output is correct |
20 |
Correct |
28 ms |
146500 KB |
Output is correct |
21 |
Correct |
47 ms |
146500 KB |
Output is correct |
22 |
Correct |
66 ms |
146500 KB |
Output is correct |
23 |
Correct |
75 ms |
146500 KB |
Output is correct |
24 |
Correct |
66 ms |
146500 KB |
Output is correct |
25 |
Correct |
42 ms |
146500 KB |
Output is correct |
26 |
Correct |
62 ms |
146500 KB |
Output is correct |
27 |
Correct |
82 ms |
146500 KB |
Output is correct |
28 |
Correct |
62 ms |
146500 KB |
Output is correct |
29 |
Correct |
63 ms |
146500 KB |
Output is correct |
30 |
Correct |
103 ms |
146500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24548 KB |
Output is correct |
3 |
Correct |
23 ms |
24548 KB |
Output is correct |
4 |
Correct |
22 ms |
24548 KB |
Output is correct |
5 |
Correct |
23 ms |
24548 KB |
Output is correct |
6 |
Correct |
26 ms |
24856 KB |
Output is correct |
7 |
Correct |
22 ms |
24856 KB |
Output is correct |
8 |
Correct |
25 ms |
24856 KB |
Output is correct |
9 |
Correct |
24 ms |
24856 KB |
Output is correct |
10 |
Correct |
25 ms |
24856 KB |
Output is correct |
11 |
Correct |
578 ms |
87884 KB |
Output is correct |
12 |
Correct |
1377 ms |
107552 KB |
Output is correct |
13 |
Correct |
459 ms |
107832 KB |
Output is correct |
14 |
Correct |
1589 ms |
146468 KB |
Output is correct |
15 |
Correct |
1560 ms |
146500 KB |
Output is correct |
16 |
Correct |
1529 ms |
146500 KB |
Output is correct |
17 |
Correct |
413 ms |
146500 KB |
Output is correct |
18 |
Correct |
3268 ms |
146500 KB |
Output is correct |
19 |
Correct |
3944 ms |
146500 KB |
Output is correct |
20 |
Correct |
1109 ms |
146500 KB |
Output is correct |
21 |
Correct |
25 ms |
146500 KB |
Output is correct |
22 |
Correct |
28 ms |
146500 KB |
Output is correct |
23 |
Correct |
28 ms |
146500 KB |
Output is correct |
24 |
Correct |
27 ms |
146500 KB |
Output is correct |
25 |
Correct |
26 ms |
146500 KB |
Output is correct |
26 |
Correct |
33 ms |
146500 KB |
Output is correct |
27 |
Correct |
26 ms |
146500 KB |
Output is correct |
28 |
Correct |
32 ms |
146500 KB |
Output is correct |
29 |
Correct |
29 ms |
146500 KB |
Output is correct |
30 |
Correct |
28 ms |
146500 KB |
Output is correct |
31 |
Correct |
47 ms |
146500 KB |
Output is correct |
32 |
Correct |
66 ms |
146500 KB |
Output is correct |
33 |
Correct |
75 ms |
146500 KB |
Output is correct |
34 |
Correct |
66 ms |
146500 KB |
Output is correct |
35 |
Correct |
42 ms |
146500 KB |
Output is correct |
36 |
Correct |
62 ms |
146500 KB |
Output is correct |
37 |
Correct |
82 ms |
146500 KB |
Output is correct |
38 |
Correct |
62 ms |
146500 KB |
Output is correct |
39 |
Correct |
63 ms |
146500 KB |
Output is correct |
40 |
Correct |
103 ms |
146500 KB |
Output is correct |
41 |
Correct |
359 ms |
146500 KB |
Output is correct |
42 |
Correct |
1370 ms |
146500 KB |
Output is correct |
43 |
Correct |
312 ms |
146500 KB |
Output is correct |
44 |
Correct |
385 ms |
146500 KB |
Output is correct |
45 |
Correct |
722 ms |
146500 KB |
Output is correct |
46 |
Correct |
998 ms |
146500 KB |
Output is correct |
47 |
Correct |
1335 ms |
146500 KB |
Output is correct |
48 |
Correct |
381 ms |
146500 KB |
Output is correct |
49 |
Correct |
1006 ms |
146500 KB |
Output is correct |
50 |
Correct |
1085 ms |
146500 KB |
Output is correct |
51 |
Correct |
330 ms |
146500 KB |
Output is correct |
52 |
Correct |
361 ms |
146500 KB |
Output is correct |
53 |
Correct |
331 ms |
146500 KB |
Output is correct |
54 |
Correct |
2037 ms |
146500 KB |
Output is correct |
55 |
Correct |
719 ms |
146500 KB |
Output is correct |