#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
constexpr int MAXN = 1e6 + 10;
struct dsu {
int par[MAXN], sz[MAXN];
dsu() {
iota(par, par + MAXN, 0);
fill(sz, sz + MAXN, 1);
}
int getPar(int v) { return par[v] == v ? v : par[v] = getPar(par[v]); }
bool merge(int u, int v) {
v = getPar(v), u = getPar(u);
if (v == u) return sz[v];
par[v] = u;
sz[u] += sz[v];
return -1;
}
} ds[5];
int N, tmp, deg[5][MAXN];
vector<int> adj[MAXN];
bool flag, can[5];
void Init(int N_) {
N = N_;
tmp = 0;
flag = false;
memset(can, true, sizeof(can));
memset(deg, 0, sizeof(deg));
rep(i, 0, 5) ds[i] = dsu();
rep(i, 0, N) adj[i].clear();
}
int bad[5];
inline void Link(int A, int B, int id) {
if (bad[id] == A || bad[id] == B) return;
deg[id][A]++, deg[id][B]++;
if (deg[id][A] == 3 || deg[id][B] == 3) can[id] = false;
if (ds[id].merge(A, B) == -1) can[id] = false;
}
inline void build(int v) {
bad[1] = v;
rep(i, 0, 3) bad[2 + i] = adj[v][i];
rep(i, 0, N) for (auto e : adj[i]) if (e > i) rep(z, 1, 5) Link(i, e, z);
}
void Link(int A, int B) {
adj[A].pb(B);
adj[B].pb(A);
if (adj[A].size() == 3) {
flag = true;
build(A);
} else if (adj[B].size() == 3) {
flag = true;
build(B);
}
if (!flag) {
int me = ds[0].merge(A, B);
if (~me) {
if (!tmp)
tmp = me;
else
tmp = -1;
}
} else
rep(i, 1, 5) Link(A, B, i);
}
int CountCritical() {
if (!flag) {
if (!tmp) return N;
if (~tmp) return tmp;
return 0;
}
int res = 0;
rep(i, 1, 5) res += can[i];
return res;
}
Compilation message
rings.cpp: In function 'void Link(int, int, int)':
rings.cpp:47:26: warning: comparison of constant '-1' with boolean expression is always false [-Wbool-compare]
if (ds[id].merge(A, B) == -1) can[id] = false;
~~~~~~~~~~~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
89 ms |
90360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
538 ms |
113616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
89 ms |
90360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
89 ms |
90360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
89 ms |
90360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |