#include <bits/stdc++.h>
using namespace std;
int N;
int dsu[1000001], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], vsId;
vector<int> adj[1000001];
bool block[1000001];
bool fn(int u, int p) {
if (vis[u] == vsId) {
return false;
}
if (!block[u] && in[u] > 2)
return false;
vis[u] = vsId;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (v == p || block[v])
continue;
if (block[u] && vis[v] == vsId)
continue;
if (!fn(v, u))
return false;
}
return true;
}
bool check(int u , int p) {
block[u] = 1;
vsId++;
for (int i = 0; i < adj[u].size(); ++i) {
in[adj[u][i]]--;
}
bool res = fn(u, p);
for (int i = 0; i < adj[u].size(); ++i) {
in[adj[u][i]]++;
}
block[u] = 0;
return res;
}
void Init(int N_) {
N = N_;
for (int i = 0; i < N; ++i) {
dsu[i] = i;
freq[i][0] = 1;
E[i] = 0;
sz[i] = 1;
}
}
int find(int u) {
return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}
void Link(int A, int B) {
adj[A].push_back(B);
adj[B].push_back(A);
freq[find(A)][in[A]]--;
freq[find(B)][in[B]]--;
in[A]++, in[B]++;
in[A] = min(in[A], 4);
in[B] = min(in[B], 4);
freq[find(A)][in[A]]++;
freq[find(B)][in[B]]++;
if (find(A) != find(B)) {
for (int i = 0 ; i <= 4 ; i++) {
if (in[A] == i) {
big[find(A)][i] = A;
}
if (in[B] == i) {
big[find(B)][i] = B;
}
}
E[find(B)] += E[find(A)];
sz[find(B)] += sz[find(A)];
for (int i = 0; i <= 4; ++i) {
big[find(B)][i] = max(big[find(B)][i], big[find(A)][i]);
freq[find(B)][i] += freq[find(A)][i];
}
dsu[find(A)] = find(B);
}
E[find(B)]++;
}
int CountCritical() {
int res = 0;
int wat = 0;
bool can = true;
for (int i = 0 ; i < N; ++i) {
if (find(i) == i) {
if (freq[i][4] > 1){
can = false;
continue;
}
int cnt = 0;
if (freq[i][4]) {
if (check(big[i][4], -1))
cnt++;
wat++;
} else if (freq[i][3]) {
if (check(big[i][3], -1)) {
cnt++;
}
for (int j = 0 ; j < adj[big[i][3]].size(); j++) {
int v = adj[big[i][3]][j];
if (check(v, -1)) {
cnt++;
}
}
if(cnt == 0)
can = false;
wat++;
} else {
if(sz[i] > 0 && E[i] != sz[i]-1){
wat++;
}
if(sz[i] && E[i] == sz[i])
cnt = sz[find(i)];
else if(sz[i] && E[i] == sz[i]-1)
cnt = sz[find(i)];
else can = false;
}
res += cnt;
}
}
if (!can || wat > 1)
res = 0;
return res;
}
Compilation message
rings.cpp: In function 'bool fn(int, int)':
rings.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); ++i) {
~~^~~~~~~~~~~~~~~
rings.cpp: In function 'bool check(int, int)':
rings.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); ++i) {
~~^~~~~~~~~~~~~~~
rings.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); ++i) {
~~^~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:108:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0 ; j < adj[big[i][3]].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
24440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
905 ms |
68912 KB |
Output is correct |
| 2 |
Incorrect |
1811 ms |
96240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
24440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
24440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
24440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
