#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 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,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) { ans = check(A); return;}
if (B == center) { ans = 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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 3 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 4 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24064 KB |
Output is correct |
| 6 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 7 |
Correct |
20 ms |
24832 KB |
Output is correct |
| 8 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 9 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 10 |
Incorrect |
22 ms |
25088 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
492 ms |
46584 KB |
Output is correct |
| 2 |
Correct |
1068 ms |
70024 KB |
Output is correct |
| 3 |
Correct |
353 ms |
49656 KB |
Output is correct |
| 4 |
Correct |
1225 ms |
80380 KB |
Output is correct |
| 5 |
Correct |
1224 ms |
80504 KB |
Output is correct |
| 6 |
Correct |
1184 ms |
78840 KB |
Output is correct |
| 7 |
Correct |
350 ms |
49272 KB |
Output is correct |
| 8 |
Correct |
1587 ms |
77688 KB |
Output is correct |
| 9 |
Incorrect |
1828 ms |
81068 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 3 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 4 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24064 KB |
Output is correct |
| 6 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 7 |
Correct |
20 ms |
24832 KB |
Output is correct |
| 8 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 9 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 10 |
Incorrect |
22 ms |
25088 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 3 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 4 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24064 KB |
Output is correct |
| 6 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 7 |
Correct |
20 ms |
24832 KB |
Output is correct |
| 8 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 9 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 10 |
Incorrect |
22 ms |
25088 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 3 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 4 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24064 KB |
Output is correct |
| 6 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 7 |
Correct |
20 ms |
24832 KB |
Output is correct |
| 8 |
Correct |
21 ms |
24064 KB |
Output is correct |
| 9 |
Correct |
21 ms |
25088 KB |
Output is correct |
| 10 |
Incorrect |
22 ms |
25088 KB |
Output isn't correct |
