This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000001;
const int CHAIN = 0;
const int CYCLE = 1;
const int THREE = 2;
const int BIG = 3;
const int BLOCKED = 4;
int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], pre[1000001], vsId, N;
vector<int> adj[1000001];
bool block[1000001];
int res = 0,ff2[10];
bool ZERO = 0;
int find(int u) {
return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}
void Init(int N_) {
N = N_;
for (int i = 0; i < N; ++i) {
dsu[i] = i;
freq[i][0] = 1;
pre[i] = 1;
res += pre[i];
E[i] = 0;
sz[i] = 1;
ff2[0]++;
}
}
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 Link(int A, int B) {
if (ZERO)
return;
adj[A].push_back(B);
adj[B].push_back(A);
if (type[find(A)] == BLOCKED || type[find(B)] == BLOCKED)
return;
if (find(A) == find(B) && (B == big[find(A)][4] || A == big[find(B)][4]))
return;
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]]++;
res -= pre[find(A)];
ff2[type[find(A)]]--;
if (find(A) != find(B)) {
ff2[type[find(B)]]--;
res -= pre[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)]++;
if (freq[find(A)][4] > 1 || freq[find(A)][3] > 4) {
type[find(A)] = BLOCKED;
ZERO = 1;
} else if (freq[find(A)][4]) {
type[find(A)] = BIG;
pre[find(A)] = 0;
if (check(big[find(A)][4], -1)) {
pre[find(A)]++;
}
res += pre[find(A)];
} else if (freq[find(A)][3]) {
type[find(A)]= THREE;
pre[find(A)] = 0;
if(check(big[find(A)][3],-1))
pre[find(A)]++;
for (int j = 0 ; j < adj[big[find(A)][3]].size(); j++) {
int v = adj[big[find(A)][3]][j];
if (check(v, -1)) {
pre[find(A)]++;
}
}
res += pre[find(A)];
} else {
if (freq[find(A)][2] == sz[find(A)]) {
type[find(A)] = CYCLE;
}
pre[find(A)] = sz[find(A)];
res += pre[find(A)];
}
ff2[type[find(A)]]++;
last[type[find(A)]] = find(A);
}
int CountCritical() {
if (ZERO)
return 0;
int fn = 0;
for (int i = 1; i <= 3; ++i){
fn += type[i];
}
if(fn > 1)
return 0;
for (int i = 1; i <= 3; ++i){
if(ff2[i]){
return pre[last[i]];
}
}
return res;
}
Compilation message (stderr)
rings.cpp: In function 'bool fn(int, int)':
rings.cpp:41: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:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); ++i) {
~~^~~~~~~~~~~~~~~
rings.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); ++i) {
~~^~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0 ; j < adj[big[find(A)][3]].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |