#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dad[N][5],ans[5],deg[N][5],lst[5],wh[5],vis[N];
int n,m,cnt;
vector <int> ed[N];
pair <int,int> edge[N];
bool flag = 0;
int find(int u,int x) {
if (dad[u][x] == u)
return dad[u][x];
return dad[u][x] = find(dad[u][x],x);
}
bool merge(int u,int v,int x) {
int du = find(u,x);
int dv = find(v,x);
if (du == dv)
return false;
dad[du][x] = dv;
return true;
}
void dfs(int cur) {
if (vis[cur])
return;
vis[cur] = 1;
cnt++;
for (auto i : ed[cur])
dfs(i);
}
int get(int cur) {
cnt = 0;
dfs(cur);
return cnt;
}
void Init(int N_) {
n = N_;
for (int i = 0 ; i < 5 ; i++) {
ans[i] = 1;
lst[i] = 1;
for (int j = 1 ; j <= n ; j++) {
dad[j][i] = j;
deg[j][i] = 0;
}
}
ans[0] = n;
}
void Link(int A, int B) {
A++ , B++;
deg[A][0]++;
deg[B][0]++;
ed[A].push_back(B);
ed[B].push_back(A);
edge[++m] = {A,B};
if (flag)
return;
if (deg[A][0] == 3) {
int t = 1;
wh[1] = A;
for (auto i : ed[A])
wh[++t] = i;
flag = true;
}
else if (deg[B][0] == 3) {
int t = 1;
wh[1] = B;
for (auto i : ed[B])
wh[++t] = i;
flag = true;
}
else if (merge(A,B,0) == false)
ans[0] != n ? ans[0] = 0 : ans[0] = get(A);
}
int CountCritical() {
if (flag == false)
return ans[0];
int res = 0;
for (int i = 1 ; i < 5 ; i++) {
if (ans[i] == 0)
continue;
for ( ; lst[i] <= m ; lst[i]++) {
int u = edge[lst[i]].first;
int v = edge[lst[i]].second;
if (u == wh[i] || v == wh[i])
continue;
deg[u][i]++;
deg[v][i]++;
if (deg[u][i] == 3 || deg[v][i] == 3 || merge(u,v,i) == false)
ans[i] = 0;
}
res += ans[i];
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
23808 KB |
Output is correct |
2 |
Correct |
26 ms |
24184 KB |
Output is correct |
3 |
Correct |
25 ms |
24320 KB |
Output is correct |
4 |
Correct |
23 ms |
23936 KB |
Output is correct |
5 |
Correct |
25 ms |
24192 KB |
Output is correct |
6 |
Correct |
26 ms |
24448 KB |
Output is correct |
7 |
Correct |
25 ms |
24064 KB |
Output is correct |
8 |
Correct |
29 ms |
24184 KB |
Output is correct |
9 |
Correct |
26 ms |
24356 KB |
Output is correct |
10 |
Correct |
27 ms |
24312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
638 ms |
64744 KB |
Output is correct |
2 |
Correct |
2107 ms |
86500 KB |
Output is correct |
3 |
Correct |
2190 ms |
97644 KB |
Output is correct |
4 |
Correct |
1588 ms |
103744 KB |
Output is correct |
5 |
Correct |
1603 ms |
108336 KB |
Output is correct |
6 |
Correct |
1815 ms |
121300 KB |
Output is correct |
7 |
Correct |
2095 ms |
98480 KB |
Output is correct |
8 |
Correct |
2657 ms |
98836 KB |
Output is correct |
9 |
Correct |
2842 ms |
103756 KB |
Output is correct |
10 |
Correct |
1189 ms |
103972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
23808 KB |
Output is correct |
2 |
Correct |
26 ms |
24184 KB |
Output is correct |
3 |
Correct |
25 ms |
24320 KB |
Output is correct |
4 |
Correct |
23 ms |
23936 KB |
Output is correct |
5 |
Correct |
25 ms |
24192 KB |
Output is correct |
6 |
Correct |
26 ms |
24448 KB |
Output is correct |
7 |
Correct |
25 ms |
24064 KB |
Output is correct |
8 |
Correct |
29 ms |
24184 KB |
Output is correct |
9 |
Correct |
26 ms |
24356 KB |
Output is correct |
10 |
Correct |
27 ms |
24312 KB |
Output is correct |
11 |
Correct |
32 ms |
24404 KB |
Output is correct |
12 |
Correct |
42 ms |
24796 KB |
Output is correct |
13 |
Correct |
31 ms |
24832 KB |
Output is correct |
14 |
Correct |
27 ms |
24576 KB |
Output is correct |
15 |
Correct |
30 ms |
24952 KB |
Output is correct |
16 |
Correct |
28 ms |
24832 KB |
Output is correct |
17 |
Correct |
32 ms |
24832 KB |
Output is correct |
18 |
Correct |
39 ms |
25464 KB |
Output is correct |
19 |
Correct |
33 ms |
24824 KB |
Output is correct |
20 |
Correct |
33 ms |
24700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
23808 KB |
Output is correct |
2 |
Correct |
26 ms |
24184 KB |
Output is correct |
3 |
Correct |
25 ms |
24320 KB |
Output is correct |
4 |
Correct |
23 ms |
23936 KB |
Output is correct |
5 |
Correct |
25 ms |
24192 KB |
Output is correct |
6 |
Correct |
26 ms |
24448 KB |
Output is correct |
7 |
Correct |
25 ms |
24064 KB |
Output is correct |
8 |
Correct |
29 ms |
24184 KB |
Output is correct |
9 |
Correct |
26 ms |
24356 KB |
Output is correct |
10 |
Correct |
27 ms |
24312 KB |
Output is correct |
11 |
Correct |
32 ms |
24404 KB |
Output is correct |
12 |
Correct |
42 ms |
24796 KB |
Output is correct |
13 |
Correct |
31 ms |
24832 KB |
Output is correct |
14 |
Correct |
27 ms |
24576 KB |
Output is correct |
15 |
Correct |
30 ms |
24952 KB |
Output is correct |
16 |
Correct |
28 ms |
24832 KB |
Output is correct |
17 |
Correct |
32 ms |
24832 KB |
Output is correct |
18 |
Correct |
39 ms |
25464 KB |
Output is correct |
19 |
Correct |
33 ms |
24824 KB |
Output is correct |
20 |
Correct |
33 ms |
24700 KB |
Output is correct |
21 |
Correct |
58 ms |
27380 KB |
Output is correct |
22 |
Correct |
74 ms |
29472 KB |
Output is correct |
23 |
Correct |
85 ms |
31040 KB |
Output is correct |
24 |
Correct |
95 ms |
30400 KB |
Output is correct |
25 |
Correct |
45 ms |
28280 KB |
Output is correct |
26 |
Correct |
85 ms |
31096 KB |
Output is correct |
27 |
Correct |
111 ms |
31728 KB |
Output is correct |
28 |
Correct |
120 ms |
31972 KB |
Output is correct |
29 |
Correct |
86 ms |
30152 KB |
Output is correct |
30 |
Correct |
141 ms |
33444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
23808 KB |
Output is correct |
2 |
Correct |
26 ms |
24184 KB |
Output is correct |
3 |
Correct |
25 ms |
24320 KB |
Output is correct |
4 |
Correct |
23 ms |
23936 KB |
Output is correct |
5 |
Correct |
25 ms |
24192 KB |
Output is correct |
6 |
Correct |
26 ms |
24448 KB |
Output is correct |
7 |
Correct |
25 ms |
24064 KB |
Output is correct |
8 |
Correct |
29 ms |
24184 KB |
Output is correct |
9 |
Correct |
26 ms |
24356 KB |
Output is correct |
10 |
Correct |
27 ms |
24312 KB |
Output is correct |
11 |
Correct |
638 ms |
64744 KB |
Output is correct |
12 |
Correct |
2107 ms |
86500 KB |
Output is correct |
13 |
Correct |
2190 ms |
97644 KB |
Output is correct |
14 |
Correct |
1588 ms |
103744 KB |
Output is correct |
15 |
Correct |
1603 ms |
108336 KB |
Output is correct |
16 |
Correct |
1815 ms |
121300 KB |
Output is correct |
17 |
Correct |
2095 ms |
98480 KB |
Output is correct |
18 |
Correct |
2657 ms |
98836 KB |
Output is correct |
19 |
Correct |
2842 ms |
103756 KB |
Output is correct |
20 |
Correct |
1189 ms |
103972 KB |
Output is correct |
21 |
Correct |
32 ms |
24404 KB |
Output is correct |
22 |
Correct |
42 ms |
24796 KB |
Output is correct |
23 |
Correct |
31 ms |
24832 KB |
Output is correct |
24 |
Correct |
27 ms |
24576 KB |
Output is correct |
25 |
Correct |
30 ms |
24952 KB |
Output is correct |
26 |
Correct |
28 ms |
24832 KB |
Output is correct |
27 |
Correct |
32 ms |
24832 KB |
Output is correct |
28 |
Correct |
39 ms |
25464 KB |
Output is correct |
29 |
Correct |
33 ms |
24824 KB |
Output is correct |
30 |
Correct |
33 ms |
24700 KB |
Output is correct |
31 |
Correct |
58 ms |
27380 KB |
Output is correct |
32 |
Correct |
74 ms |
29472 KB |
Output is correct |
33 |
Correct |
85 ms |
31040 KB |
Output is correct |
34 |
Correct |
95 ms |
30400 KB |
Output is correct |
35 |
Correct |
45 ms |
28280 KB |
Output is correct |
36 |
Correct |
85 ms |
31096 KB |
Output is correct |
37 |
Correct |
111 ms |
31728 KB |
Output is correct |
38 |
Correct |
120 ms |
31972 KB |
Output is correct |
39 |
Correct |
86 ms |
30152 KB |
Output is correct |
40 |
Correct |
141 ms |
33444 KB |
Output is correct |
41 |
Correct |
335 ms |
55216 KB |
Output is correct |
42 |
Correct |
951 ms |
77832 KB |
Output is correct |
43 |
Correct |
370 ms |
65784 KB |
Output is correct |
44 |
Correct |
840 ms |
96768 KB |
Output is correct |
45 |
Correct |
844 ms |
90240 KB |
Output is correct |
46 |
Correct |
1083 ms |
91096 KB |
Output is correct |
47 |
Correct |
1520 ms |
103804 KB |
Output is correct |
48 |
Correct |
636 ms |
83648 KB |
Output is correct |
49 |
Correct |
982 ms |
95816 KB |
Output is correct |
50 |
Correct |
1171 ms |
94840 KB |
Output is correct |
51 |
Correct |
387 ms |
62584 KB |
Output is correct |
52 |
Correct |
751 ms |
83596 KB |
Output is correct |
53 |
Correct |
577 ms |
84312 KB |
Output is correct |
54 |
Correct |
1934 ms |
88820 KB |
Output is correct |
55 |
Correct |
1423 ms |
94332 KB |
Output is correct |