#include<bits/stdc++.h>
using namespace std;
int n,cycle_size,cycles;
vector<int> adj[1000001];
bool flag = 1;
int sz[1000001],SZ[1000001], P[1000001] , ans, center = -1,help,seen[1000001],change,d;
bool bad[1000001],good[1000001];
set<int> more_than4;
int par(int a) {
if (a != P[a])
return P[a] = par(P[a]);
return a;
}
void join(int a,int b) {
int x = par(a);
int y = par(b);
if (x == y) return;
if (SZ[x] > SZ[y]) swap(x,y);
P[x] = y;
SZ[y] += SZ[x];
}
void Init(int N) {
ans = n = N;
for (int i = 0 ; i < n; i++)
P[i] = i,good[i] = SZ[i] = 1;
}
int vis[1000001];
void dfs (int v,int p,int X) {
if (sz[v] >= 3)
flag = 0;
vis[v] = help;
for (int i: adj[v]) {
if (i == p || i == X) continue;
if (vis[i] == help) {
flag = 0;
}else dfs(i,v,X);
}
}
bool check(int v) {
if (!good[v]) return 0;
help++;
flag = 1;
for (int i : adj[v]) sz[i]--;
for (int i = 0; i < n; i++)
if (i != v && help != vis[i]) dfs(i,-1,v);
for (int i : adj[v]) sz[i]++;
good[v] = flag;
return flag;
}
vector<int> dangerous;
void add(int x) {
if (bad[x]) return;
bad[x] = 1; dangerous.push_back(x);
}
void Link(int A, int B) {
if (ans == 0) return;
if (center != B)
sz[A]++;
if (center != A)
sz[B]++;
adj[A].push_back(B);
adj[B].push_back(A);
if (center != -1) {
if (!d) {
for (int i = 0 ; i < n; i++)
P[i] = i, SZ[i] = 1,sz[i]= 0;
for (int i = 0; i < n; i ++)
if (i != center)
for (int j : adj[i])
if (j != center)
join(j,i),sz[i]++;
d = 1;
}
if (A != center && B != center) {
if (sz[A] >= 3 || sz[B] >= 3) {ans = 0; return;}
int x = par(A), y = par(B);
join(A,B);
if (sz[A] == 1 || sz[B] == 1) return;
if (x != y) return;
ans = 0; return;
}
}
if (sz[A] == 3) {change = 1;add(A);for (int i:adj[A]) add(i);}
if (sz[B] == 3) {change = 1;add(B);for (int i : adj[B]) add(i);}
if (sz[A] >= 4) more_than4.insert(A),change = 1;
if (sz[B] >= 4) more_than4.insert(B),change = 1;
if (more_than4.size() >= 2) { ans = 0; return; }
if (A == center || B == center ) { change = 0; return;}
int x = par(A), y = par(B);
join(A,B);
if (x != y && sz[A] <= 2 && sz[B] <= 2 ) return;
if (more_than4.size()) center = *more_than4.begin();
if (A == center) { ans = check(A); return;}
if (B == center) { ans = check(B); return;}
if (sz[A]>= 3 || sz[B] >= 3) {
if (center != -1 ) {
ans = check(center);
return;
}
int t = 0;
for (int j : dangerous) t += check(j);
ans = t;
return;
}
if (sz[A] == 1 || sz[B] == 1) return;
if (x == y && sz[A] == 2 && sz[B] == 2) {
if (dangerous.empty()) {
if (cycles) { ans = 0; return;}
cycles = 1;
cycle_size = SZ[par(A)];
ans = cycle_size;
return ;
} else {
int t = 0;
if (center != -1 ){
ans = check(center);
return;
}
for (int j : dangerous) t += check(j);
ans = t;
return;
}
}
}
int CountCritical() {
return ans;
}
Compilation message
rings.cpp: In function 'void Init(int)':
rings.cpp:26:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
P[i] = i,good[i] = SZ[i] = 1;
~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23808 KB |
Output is correct |
2 |
Correct |
21 ms |
24064 KB |
Output is correct |
3 |
Correct |
21 ms |
24064 KB |
Output is correct |
4 |
Correct |
20 ms |
23936 KB |
Output is correct |
5 |
Correct |
20 ms |
23936 KB |
Output is correct |
6 |
Correct |
20 ms |
24064 KB |
Output is correct |
7 |
Correct |
20 ms |
23936 KB |
Output is correct |
8 |
Correct |
19 ms |
24064 KB |
Output is correct |
9 |
Correct |
23 ms |
24192 KB |
Output is correct |
10 |
Correct |
22 ms |
24192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
478 ms |
46804 KB |
Output is correct |
2 |
Correct |
1320 ms |
62248 KB |
Output is correct |
3 |
Correct |
408 ms |
40952 KB |
Output is correct |
4 |
Correct |
1200 ms |
67960 KB |
Output is correct |
5 |
Correct |
1231 ms |
67772 KB |
Output is correct |
6 |
Correct |
1168 ms |
66816 KB |
Output is correct |
7 |
Correct |
413 ms |
41160 KB |
Output is correct |
8 |
Correct |
2721 ms |
68856 KB |
Output is correct |
9 |
Correct |
3772 ms |
71864 KB |
Output is correct |
10 |
Correct |
884 ms |
66296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23808 KB |
Output is correct |
2 |
Correct |
21 ms |
24064 KB |
Output is correct |
3 |
Correct |
21 ms |
24064 KB |
Output is correct |
4 |
Correct |
20 ms |
23936 KB |
Output is correct |
5 |
Correct |
20 ms |
23936 KB |
Output is correct |
6 |
Correct |
20 ms |
24064 KB |
Output is correct |
7 |
Correct |
20 ms |
23936 KB |
Output is correct |
8 |
Correct |
19 ms |
24064 KB |
Output is correct |
9 |
Correct |
23 ms |
24192 KB |
Output is correct |
10 |
Correct |
22 ms |
24192 KB |
Output is correct |
11 |
Correct |
23 ms |
24192 KB |
Output is correct |
12 |
Correct |
28 ms |
24448 KB |
Output is correct |
13 |
Correct |
27 ms |
24448 KB |
Output is correct |
14 |
Correct |
21 ms |
24192 KB |
Output is correct |
15 |
Correct |
22 ms |
24448 KB |
Output is correct |
16 |
Correct |
26 ms |
24312 KB |
Output is correct |
17 |
Correct |
21 ms |
24064 KB |
Output is correct |
18 |
Correct |
23 ms |
24320 KB |
Output is correct |
19 |
Correct |
24 ms |
24320 KB |
Output is correct |
20 |
Correct |
26 ms |
24448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23808 KB |
Output is correct |
2 |
Correct |
21 ms |
24064 KB |
Output is correct |
3 |
Correct |
21 ms |
24064 KB |
Output is correct |
4 |
Correct |
20 ms |
23936 KB |
Output is correct |
5 |
Correct |
20 ms |
23936 KB |
Output is correct |
6 |
Correct |
20 ms |
24064 KB |
Output is correct |
7 |
Correct |
20 ms |
23936 KB |
Output is correct |
8 |
Correct |
19 ms |
24064 KB |
Output is correct |
9 |
Correct |
23 ms |
24192 KB |
Output is correct |
10 |
Correct |
22 ms |
24192 KB |
Output is correct |
11 |
Correct |
23 ms |
24192 KB |
Output is correct |
12 |
Correct |
28 ms |
24448 KB |
Output is correct |
13 |
Correct |
27 ms |
24448 KB |
Output is correct |
14 |
Correct |
21 ms |
24192 KB |
Output is correct |
15 |
Correct |
22 ms |
24448 KB |
Output is correct |
16 |
Correct |
26 ms |
24312 KB |
Output is correct |
17 |
Correct |
21 ms |
24064 KB |
Output is correct |
18 |
Correct |
23 ms |
24320 KB |
Output is correct |
19 |
Correct |
24 ms |
24320 KB |
Output is correct |
20 |
Correct |
26 ms |
24448 KB |
Output is correct |
21 |
Correct |
37 ms |
25516 KB |
Output is correct |
22 |
Correct |
49 ms |
26488 KB |
Output is correct |
23 |
Correct |
59 ms |
27256 KB |
Output is correct |
24 |
Correct |
62 ms |
27128 KB |
Output is correct |
25 |
Correct |
35 ms |
26104 KB |
Output is correct |
26 |
Correct |
64 ms |
28584 KB |
Output is correct |
27 |
Correct |
65 ms |
28280 KB |
Output is correct |
28 |
Correct |
51 ms |
26488 KB |
Output is correct |
29 |
Correct |
51 ms |
26488 KB |
Output is correct |
30 |
Correct |
83 ms |
29464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
23808 KB |
Output is correct |
2 |
Correct |
21 ms |
24064 KB |
Output is correct |
3 |
Correct |
21 ms |
24064 KB |
Output is correct |
4 |
Correct |
20 ms |
23936 KB |
Output is correct |
5 |
Correct |
20 ms |
23936 KB |
Output is correct |
6 |
Correct |
20 ms |
24064 KB |
Output is correct |
7 |
Correct |
20 ms |
23936 KB |
Output is correct |
8 |
Correct |
19 ms |
24064 KB |
Output is correct |
9 |
Correct |
23 ms |
24192 KB |
Output is correct |
10 |
Correct |
22 ms |
24192 KB |
Output is correct |
11 |
Correct |
478 ms |
46804 KB |
Output is correct |
12 |
Correct |
1320 ms |
62248 KB |
Output is correct |
13 |
Correct |
408 ms |
40952 KB |
Output is correct |
14 |
Correct |
1200 ms |
67960 KB |
Output is correct |
15 |
Correct |
1231 ms |
67772 KB |
Output is correct |
16 |
Correct |
1168 ms |
66816 KB |
Output is correct |
17 |
Correct |
413 ms |
41160 KB |
Output is correct |
18 |
Correct |
2721 ms |
68856 KB |
Output is correct |
19 |
Correct |
3772 ms |
71864 KB |
Output is correct |
20 |
Correct |
884 ms |
66296 KB |
Output is correct |
21 |
Correct |
23 ms |
24192 KB |
Output is correct |
22 |
Correct |
28 ms |
24448 KB |
Output is correct |
23 |
Correct |
27 ms |
24448 KB |
Output is correct |
24 |
Correct |
21 ms |
24192 KB |
Output is correct |
25 |
Correct |
22 ms |
24448 KB |
Output is correct |
26 |
Correct |
26 ms |
24312 KB |
Output is correct |
27 |
Correct |
21 ms |
24064 KB |
Output is correct |
28 |
Correct |
23 ms |
24320 KB |
Output is correct |
29 |
Correct |
24 ms |
24320 KB |
Output is correct |
30 |
Correct |
26 ms |
24448 KB |
Output is correct |
31 |
Correct |
37 ms |
25516 KB |
Output is correct |
32 |
Correct |
49 ms |
26488 KB |
Output is correct |
33 |
Correct |
59 ms |
27256 KB |
Output is correct |
34 |
Correct |
62 ms |
27128 KB |
Output is correct |
35 |
Correct |
35 ms |
26104 KB |
Output is correct |
36 |
Correct |
64 ms |
28584 KB |
Output is correct |
37 |
Correct |
65 ms |
28280 KB |
Output is correct |
38 |
Correct |
51 ms |
26488 KB |
Output is correct |
39 |
Correct |
51 ms |
26488 KB |
Output is correct |
40 |
Correct |
83 ms |
29464 KB |
Output is correct |
41 |
Correct |
271 ms |
42444 KB |
Output is correct |
42 |
Correct |
918 ms |
60852 KB |
Output is correct |
43 |
Correct |
294 ms |
46328 KB |
Output is correct |
44 |
Correct |
371 ms |
51832 KB |
Output is correct |
45 |
Correct |
1078 ms |
58180 KB |
Output is correct |
46 |
Correct |
833 ms |
72144 KB |
Output is correct |
47 |
Correct |
1058 ms |
73464 KB |
Output is correct |
48 |
Correct |
380 ms |
49016 KB |
Output is correct |
49 |
Correct |
810 ms |
72744 KB |
Output is correct |
50 |
Correct |
842 ms |
72316 KB |
Output is correct |
51 |
Correct |
331 ms |
46264 KB |
Output is correct |
52 |
Correct |
340 ms |
47236 KB |
Output is correct |
53 |
Correct |
337 ms |
48316 KB |
Output is correct |
54 |
Correct |
2167 ms |
74448 KB |
Output is correct |
55 |
Correct |
1113 ms |
78744 KB |
Output is correct |