#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6 + 5;
static int n;
static vector<int> ciclu;
static vector<int> cen, g3, trk;
struct Str {
bool valid;
int c1[nmax + 1], c2[nmax + 1];
int grad[nmax + 1], t[nmax + 1];
vector<int> g[nmax + 1];
void init () {
valid = 1;
for (int i = 0; i < n; ++ i) {
grad[i] = 1;
t[i] = c1[i] = c2[i] = i;
}
}
inline int find_tata (int x) {
if (x == t[x]) return x;
return t[x] = find_tata(t[x]);
}
void link (int A, int B) {
if (valid == 0)
return ;
g[A].push_back(B);
g[B].push_back(A);
if (g[A].size() < 3 && g[B].size() < 3) {
int la = find_tata(A);
int lb = find_tata(B);
if (la == lb) { // apare ciclu
valid = 0;
} else {
if (grad[la] < grad[lb]) {
swap(la, lb);
swap(A, B);
}
grad[la] += grad[lb];
t[lb] = la;
if (A == c1[la]) {
c1[la] = c1[lb] + c2[lb] - B;
} else {
c2[la] = c1[lb] + c2[lb] - B;
}
}
} else
valid = 0;
}
} root, centered, s3[12];
static vector<pair<int, int>> e;
static map<pair<int, int>, bool> mp;
void Init(int N_) {
n = N_;
root.init();
}
bool nuexista (int i) {
bool ok = 1;
for (auto j : trk)
if (i == j) ok = 0;
return ok;
}
void Link(int A, int B) {
e.push_back({A, B});
mp[{A, B}] = mp[{B, A}] = 1;
if (root.g[A].size() == 1 && root.g[B].size() == 1 && root.find_tata(A) == root.find_tata(B)) {
ciclu.push_back(root.grad[root.find_tata(A)]);
}
root.link(A, B);
int oldcen = cen.size();
int old3 = trk.size();
if (cen.size() == 0 && (root.g[A].size() >= 3 || root.g[B].size() >= 3)) {
if (g3.size() > 3)
return ;
if (root.g[A].size() == 3) {
g3.push_back(A);
if (nuexista(A))
trk.push_back(A);
for (auto i : root.g[A]) {
if (nuexista(i))
trk.push_back(i);
}
}
if (root.g[B].size() == 3) {
g3.push_back(B);
if (nuexista(B))
trk.push_back(B);
for (auto i : root.g[B]) {
if (nuexista(i))
trk.push_back(i);
}
}
if (root.g[A].size() > 3) cen.push_back(A);
if (root.g[B].size() > 3) cen.push_back(B);
}
// dc nu exista cen, at tin pentru cele 3 g3 uri cum arata fara fiecare
if (cen.size() == 0) {
if (g3.size() > 3)
return ;
for (int i = old3; i < (int)trk.size(); ++ i) {
s3[i].init();
for (auto j : e)
if (j.first != trk[i] && j.second != trk[i])
s3[i].link(j.first, j.second);
}
for (int i = 0; i < old3; ++ i)
if (A != trk[i] && B != trk[i])
s3[i].link(A, B);
}
if (oldcen == 0 && cen.size() == 1) { // a aparut bossu refac tot
centered.init();
for (auto i : e)
if (i.first != cen[0] && i.second != cen[0])
centered.link(i.first, i.second);
}
if (cen.size() == 1 && oldcen == 1)
if (A != cen[0] && B != cen[0])
centered.link(A, B);
}
int CountCritical() {
if (ciclu.size() > 1 || cen.size() > 1) {
return 0;
}
if (g3.size() == 0) {
if (ciclu.size() == 0)
return n;
return ciclu[0];
} else {
if (cen.size() == 0 && g3.size() > 3) // daca sunt 4+ trebuie sa aiba un centru
return 0;
if (cen.size()) {
return centered.valid;
} else {
int cnt = 0;
for (int i = 0; i < (int)trk.size(); ++ i) {
cnt += s3[i].valid;
}
return cnt;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
220 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
231 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
220 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
220 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
220 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
