#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!= -1) {
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;
for (int i = 0; i < n; i ++)
if (i != center)
for (int j : adj[i])
if (i != j)
join(j,i),sz[j]++;
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;
~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
24064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
481 ms |
44756 KB |
Output is correct |
| 2 |
Incorrect |
939 ms |
56056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
24064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
24064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
24064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
