#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e6+10;
// graph data
int n;
vector<pii> E, ES;
vector<int> G[N];
int dfs(int u, int p, int s, int t)
{
if (u == t)
return 1;
for (auto v : G[u]) if (v != p && (u != s || v != t)) {
int r = dfs(v, u, s, t);
if (r) return r+1;
}
return 0;
}
// dsu with copying for experimentation
int par[N], mfcnt, firstcycle;
int root(int u) {
if (par[u] == u) return u;
return par[u] = root(par[u]);
}
bool merge(int u, int v) {
//fprintf(stderr, "merge(%d, %d)\n", u, v);
u = root(u), v = root(v);
if (u == v) {
if (++mfcnt == 1)
firstcycle = dfs(u, -1, u, v);
return false;
}
par[u] = v;
return true;
}
int _np[N], _nv[N], nmfcnt, tick;
int &np(int u) {
if (_nv[u] != tick) {
_np[u] = par[u];
_nv[u] = tick;
}
return _np[u];
}
int nroot(int u) {
if (np(u) == u) return u;
return np(u) = nroot(np(u));
}
bool nmerge(int u, int v) {
//fprintf(stderr, "nmerge(%d, %d)\n", u, v);
u = nroot(u), v = nroot(v);
if (u == v) return ++nmfcnt, false;
np(u) = v;
return true;
}
// state control (degree freq. histogram)
int cntok, cnt3, cnt4;
pii mxdeg(0, -1);
void testmod(int a, int b) {
if (a <= 2) --cntok;
if (a == 3) --cnt3;
if (a >= 4) --cnt4;
if (b <= 2) ++cntok;
if (b == 3) ++cnt3;
if (b >= 4) ++cnt4;
}
// rebuild dsu with exceptions
bool must_skip(int u) {
if (mxdeg.first < 3)
return false;
if (u == mxdeg.second)
return true;
if (mxdeg.first == 3) {
for (auto v : G[mxdeg.second]) if (v == u)
return true;
}
return false;
}
void build_dsu() {
//fprintf(stderr, "rebuild dsu!\n");
ES.clear();
for (int i = 0; i < n; ++i)
par[i] = i;
for (auto e : E) {
int u = e.first, v = e.second;
if (must_skip(u) || must_skip(v)) {
ES.emplace_back(u, v);
//fprintf(stderr, "skip edge %d %d\n", u, v);
continue;
}
merge(e.first, e.second);
}
}
bool modify(int u) {
testmod(G[u].size()-1, G[u].size());
if (G[u].size() > mxdeg.first) {
mxdeg = pii(G[u].size(), u);
if (mxdeg.first == 3 || mxdeg.first == 4)
return true;
}
return false;
}
// testing functions
bool test(int u) {
//fprintf(stderr, "test(%d)\n", u);
testmod(G[u].size(), G[u].size()-1);
for (auto v : G[u])
testmod(G[v].size(), G[v].size()-1);
bool ok = cnt3 == 0 && cnt4 == 0;
/*++tick;
nmfcnt = mfcnt;
if (ok) for (auto e : ES) {
if (e.first == u || e.second == u) continue;
if (!nmerge(e.first, e.second)) ok = false;
if (!ok) break;
}
if (nmfcnt > 0) ok = false;*/
for (int u = 0; u < n; ++u)
par[u] = u;
for (auto e : E) {
if (e.first == u || e.second == u) continue;
if (!merge(e.first, e.second)) ok = false;
if (!ok) break;
}
testmod(G[u].size()-1, G[u].size());
for (auto v : G[u])
testmod(G[v].size()-1, G[v].size());
return ok;
}
// problem functions:
void Init(int n) {
//fprintf(stderr, "Init(%d)\n", n);
::n = n;
build_dsu();
}
void Link(int u, int v) {
//fprintf(stderr, "Link(%d, %d)\n", u, v);
G[u].push_back(v);
G[v].push_back(u);
bool m = modify(u) | modify(v);
E.emplace_back(u, v);
if (m)
build_dsu();
else if (!must_skip(u) && !must_skip(v))
merge(u, v);
else
ES.emplace_back(u, v);
}
int CountCritical() {
//fprintf(stderr, "CountCritical()\n");
if (mxdeg.first <= 2) {
if (mfcnt > 1) return 0;
else if (mfcnt == 1) return firstcycle;
else return n;
}
int cnt = 0;
for (int u = 0; u < n; ++u)
if (test(u)) ++cnt;
return cnt;
/*if (mxdeg.first == 3) {
int cnt = 0;
if (test(mxdeg.second)) ++cnt;
for (auto v : G[mxdeg.second])
if (test(v)) ++cnt;
return cnt;
}
if (cnt4 > 1) return 0;
return test(mxdeg.second) ? 1 : 0;*/
}
Compilation message
rings.cpp: In function 'bool modify(int)':
rings.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (G[u].size() > mxdeg.first) {
~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
24208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
444 ms |
46416 KB |
Output is correct |
| 2 |
Execution timed out |
4037 ms |
58408 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
24208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
24208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
24208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
