#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;
set<int> more_than4;
int par(int a) {
if (a != P[a])
return a = par(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,SZ[i] = 1;
}
bool vis[1000001];
void dfs (int v,int p,int X) {
if (sz[v] >= 3)
flag = 0;
vis[v] = 1;
for (int i: adj[v]) {
if (i == p || i == X) continue;
if (vis[i]) {
flag = 0;
}else dfs(i,v,X);
}
}
bool check(int v) {
flag = 1;
memset(vis,0,sizeof vis);
for (int i : adj[v]) sz[i]--;
for (int i = 0; i < n; i++)
if (i != v && !vis[i]) dfs(i,-1,v);
for (int i : adj[v]) sz[i]++;
return flag;
}
vector<int> dangerous;
void Link(int A, int B) {
if (ans == 0) return;
sz[A]++;
sz[B]++;
adj[A].push_back(B);
adj[B].push_back(A);
if (sz[A] == 3) dangerous.push_back(A);
if (sz[B] == 3) dangerous.push_back(B);
if (sz[A] >= 4) more_than4.insert(A);
if (sz[B] >= 4) more_than4.insert(B);
if (more_than4.size() >= 2) { ans = 0; return; }
if (center != - 1 && (A == center || B == center) ) return;
if (more_than4.size()) center = *more_than4.begin();
if (A == center) { check(A); return;}
if (B == center) { check(B); return;}
int x = par(A), y = par(B);
join(A,B);
if (x != y && sz[A] <= 2 && sz[B] <= 2 ) return;
if (sz[A]>= 3 || sz[B] >= 3) {
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()) {
cycles++;
cycle_size = SZ[par(A)];
if (cycles > 1) { ans = 0; return;}
ans = cycle_size;
return;
} else {
int t = 0;
for (int j : dangerous) t += check(j);
ans = t;
return;
}
}
}
int CountCritical() {
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4086 ms |
23808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4083 ms |
28416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4086 ms |
23808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4086 ms |
23808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4086 ms |
23808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
