#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
using ll = long long;
constexpr int MAXN = 5+1e6;
struct dsu {
private:
vector<int> f,sz;
public:
dsu() = default;
void reset(int n) {
sz.assign(n, 1); f.resize(n);
for (int i = 0; i < n; ++i) f[i] = i;
}
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
bool join(int x, int y) {
if ((x = find(x)) == (y = find(y))) return false;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y];
f[y] = x;
return true;
}};
namespace data {
vector<ii> history; // OK!
set<int> active; // OK!
int deg[MAXN]; // OK!
dsu* graphs[MAXN]; // OK!
set<int> byd[5]; // OK!
int phase; // OK!
dsu general; // OK!
int N; // OK!
vector<int> G[MAXN]; // OK!
bool visited[MAXN]; // OK!
bool okPhase2; // OK!
vector<int> endPointsPhase2; // OK!
int degPhase3[MAXN], rootPhase3;
bool okPhase3;
int* degPhase4[MAXN];
bool initPhase4[MAXN]; // OK!
bool okPhase4[MAXN];
void keep_only(const set<int>& keep) {
for (set<int>::iterator it = active.begin(), nx; it != active.end(); it = nx) {
nx = next(it);
if (keep.find(*it) == keep.end()) {
active.erase(it);
}
}
}
void initializePhase3(int u) {
// assert(graphs[u] == nullptr);
okPhase3 = true;
rootPhase3 = u;
for (int i = 0; i < N; ++i) {
degPhase3[i] = 0;
}
graphs[u] = new dsu();
graphs[u]->reset(N);
for (auto x : history) {
if (x.first == u || x.second == u) continue;
okPhase3 &= (++degPhase3[x.first] <= 2);
okPhase3 &= (++degPhase3[x.second] <= 2);
okPhase3 &= (graphs[rootPhase3]->join(x.first, x.second));
}
if (!okPhase3) {
keep_only({});
}
}
void initPhase4PerNode(int u) {
// assert(!initPhase4[u]);
// assert(degPhase4[u] == nullptr);
initPhase4[u] = true;
okPhase4[u] = true;
graphs[u] = new dsu(); graphs[u]->reset(N);
degPhase4[u] = new int[N];
for (int i = 0; i < N; ++i) degPhase4[u][i] = 0;
for (auto x : history) {
if (x.first == u || x.second == u) continue;
okPhase4[u] &= (++degPhase4[u][x.first] <= 2);
okPhase4[u] &= (++degPhase4[u][x.second] <= 2);
okPhase4[u] &= (graphs[u]->join(x.first, x.second));
}
}
void restart_visit() {
fill(visited, visited+N, false);
}
void reset(int n) {
N=n;
history.clear();
active.clear();
for (int i = 0; i < 5; ++i) byd[i].clear();
for (int i = 0; i < n; ++i) {
deg[i] = 0;
G[i].clear();
if (graphs[i] != nullptr) {
delete graphs[i];
graphs[i] = nullptr;
}
if (degPhase4[i] != nullptr) {
delete degPhase4[i];
degPhase4[i] = nullptr;
}
active.insert(i);
byd[0].insert(i);
initPhase4[i] = false;
}
phase = 1;
general.reset(n);
okPhase2 = true;
endPointsPhase2.clear();
}}
void Init(int N) {
data::reset(N);
}
bool dfs(int A, int B, set<int>& path) {
data::visited[A] = true;
if (A == B) {
path.insert(A);
return true;
}
for (int v : data::G[A]) {
if (!data::visited[v] && dfs(v, B, path)) {
path.insert(A);
return true;
}
}
return false;
}
void Link(int A, int B) {
data::history.push_back({A,B});
using namespace data;
if (active.empty()) return;
byd[deg[A]].erase(A);
byd[deg[B]].erase(B);
deg[A] = min(1+deg[A], 4);
deg[B] = min(1+deg[B], 4);
byd[deg[A]].insert(A);
byd[deg[B]].insert(B);
int largest = -1;
for (int i = 4; i >= 0; --i) {
if ((int)byd[i].size() >= 1) {
largest = i;
break;
}
}
assert(largest != -1);
if (phase == 1) {
assert(largest >= 0 && largest <= 2);
if (largest == 2) phase = 2;
} else if (phase == 2) {
assert(largest >= 2);
if (largest == 3) phase = 4;
} else if (phase == 4) {
assert(largest >= 3);
if (largest == 4) phase = 5;
}
if (phase == 1) {
//cout << "Phase 1" << endl;
// assert(general.join(A,B));
G[A].push_back(B);
G[B].push_back(A);
} else if (phase == 2) {
//cout << "Phase 2" << endl;
bool f = general.join(A,B);
if (!f) {
if (okPhase2) {
set<int> path;
restart_visit();
dfs(A,B,path);
keep_only(path);
okPhase2 = false;
endPointsPhase2.push_back(A);
endPointsPhase2.push_back(B);
} else {
auto it = find(endPointsPhase2.begin(), endPointsPhase2.end(), A);
auto it2 = find(endPointsPhase2.begin(), endPointsPhase2.end(), B);
vector<int>::iterator de = endPointsPhase2.end();
if (it != endPointsPhase2.end()) {
de = it;
endPointsPhase2.erase(it2);
} else if (it2 != endPointsPhase2.end()) {
de = it2;
endPointsPhase2.erase(it);
} else {
keep_only({});
endPointsPhase2.clear();
}
if (de != endPointsPhase2.end()) {
keep_only({*de});
initializePhase3(*de);
phase = 3;
}
}
}
G[A].push_back(B);
G[B].push_back(A);
} else if (phase == 3) {
if (A == rootPhase3 || B == rootPhase3) return;
okPhase3 &= graphs[rootPhase3]->join(A,B);
okPhase3 &= (++degPhase3[A] <= 2);
okPhase3 &= (++degPhase3[B] <= 2);
if (!okPhase3) keep_only({});
} else if (phase == 4) {
G[A].push_back(B);
G[B].push_back(A);
const int sz = (int)byd[3].size();
assert(sz>0);
int fNode = *byd[3].begin();
set<int> check;
if (sz >= 5) {
keep_only({});
} else if (sz >= 1 && sz <= 4) {
for (auto x : G[fNode]) {
bool ok = true;
for (auto u : byd[3]) {
if (find(G[u].begin(), G[u].end(), x) == G[u].end()) {
ok = false;
break;
}
}
if (ok) {
check.insert(x);
}
}
for (auto u : byd[3]) check.insert(u);
} else {
// assert(false);
}
keep_only(check);
set<int> keep;
for (auto x : active) {
if (!initPhase4[x]) {
initPhase4PerNode(x);
} else {
if (A != x && B != x) {
okPhase4[x] &= (++degPhase4[x][A] <= 2);
okPhase4[x] &= (++degPhase4[x][B] <= 2);
okPhase4[x] &= (graphs[x]->join(A,B));
}
}
if (okPhase4[x]) {
keep.insert(x);
}
}
keep_only(keep);
} else if (phase == 5) {
assert(!byd[4].empty());
if ((int)byd[4].size() == 1) {
keep_only({*byd[4].begin()});
initializePhase3(*byd[4].begin());
phase = 3;
} else if ((int)byd[4].size() >= 2) {
keep_only({});
}
}
}
int CountCritical() {
return (int)data::active.size();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
24704 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24832 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
24040 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2937 ms |
99872 KB |
Output is correct |
| 2 |
Execution timed out |
4105 ms |
173292 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
24704 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24832 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
24040 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
24704 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24832 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
24040 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
24704 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24832 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
24040 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
