//#include "rings.h"
#include <bits/stdc++.h>
using namespace std;
const int DIM = 1e6 + 5;
int ans;
int tip; /// 0 daca nu am restrictii, 1 daca am un ciclu simplu, 2 daca deja am putini candidati
int which; ///ce lant e ciclu simplu
int r1, r2; ///lanturile pe care am nodurile critice
int n;
int gr[DIM];
int tt[DIM], sz[DIM];
vector <int> cand;
vector <int> adj[DIM];
deque <int> lant[DIM];
void Init(int N_) {
n = N_; ans = n; tip = 0;
for (int i = 0; i < n ; ++i) {
tt[i] = i, sz[i] = 1;
lant[i].push_back(i);
}
}
int find(int nod) {
if (nod != tt[nod]) return (tt[nod] = find(tt[nod]));
return nod;
}
void get_cand(int A, vector <int> &cand) {
if (gr[A] >= 4) cand.push_back(A);
else if (gr[A] == 3) {
cand.push_back(A);
for (auto it : adj[A]) cand.push_back(it);
}
}
void unite(vector <int> &cand, vector <int> candA, vector <int> candB) {
cand.clear();
if (candA.empty()) cand = candB;
else if (candB.empty()) cand = candA;
else {
for (auto itA : candA)
for (auto itB : candB)
if (itA == itB) {cand.push_back(itA); break ;}
}
}
bool viz[DIM], ign[DIM], mark[DIM];
bool check(int nod, int papa = -1) {
viz[nod] = true;
for (auto it : adj[nod]) {
if (ign[it]) continue ;
if (it == papa) continue ;
if (viz[it]) return false;
check(it, nod);
}
return true;
}
void f(int A, int B, int rA, int rB) {
mark[rA] = mark[rB] = 1;
if (tip == 0) {
tip = 2;
vector <int> candB;
get_cand(A, cand);
get_cand(B, candB);
unite(cand, cand, candB);
}
else if (tip == 2) {
vector <int> candA, candB;
get_cand(A, candA);
get_cand(B, candB);
unite(candA, candA, candB);
unite(cand, cand, candA);
}
else if (tip == 1) {
if (find(which) == rB) swap(A, B), swap(rA, rB);
if (find(which) == rA) {
tip = 2;
vector <int> candB;
get_cand(A, cand);
get_cand(B, candB);
unite(cand, cand, candB);
vector <int> candA;
for (auto it : cand)
if (find(it) == rA) candA.push_back(it);
cand.clear();
cand = candA;
} else cand.clear();
}
vector <int> candA;
for (auto it : cand) {
ign[it] = 1;
memset(viz, 0, sizeof(viz));
bool ok = true;
for (auto x : adj[it]) {
if (viz[x]) continue ;
ok = check(x);
if (!ok) break ;
}
if (ok) candA.push_back(it);
ign[it] = 0;
}
cand.clear();
cand = candA;
ans = cand.size();
}
void Link(int A, int B) {
if (ans == 0) return ;
++gr[A]; ++gr[B];
adj[A].push_back(B);
adj[B].push_back(A);
int rA = find(A), rB = find(B);
if (rA == rB) {
if (gr[A] == gr[B] && gr[A] == 2) {
///am creat un ciclu simplu
if (tip == 0) {
tip = 1;
which = find(A);
ans = sz[rA];
mark[rA] = 1;
} else if (tip == 1) {
ans = 0;
return ;
} else {
vector <int> candA;
for (auto it : cand)
if (find(it) == rA) candA.push_back(it);
cand.clear();
cand = candA;
}
} else {
///am creat (cel putin) un nod de grad 3
f(A, B, rA, rB);
}
} else {
///TODO : sa am grija cand unesc 2 lanturi pe care le-am 'legat' deja la mijloc
if (!(mark[rA] || mark[rB]) && gr[A] <= 2 && gr[B] <= 2 && (A == lant[rA].back() || A == lant[rA].front()) && (B == lant[rB].back() || B == lant[rB].front())) {
///cazul lejer in care unesc 2 lanturi
if (sz[rA] < sz[rB]) swap(A, B), swap(rA, rB);
sz[rA] += sz[rB]; tt[rB] = rA;
if (A == lant[rA].back() && B == lant[rB].front()) {
for (auto it : lant[rB]) lant[rA].push_back(it);
} else if (A == lant[rA].back() && B == lant[rB].back()) {
while (!lant[rB].empty()) {
lant[rA].push_back(lant[rB].back());
lant[rB].pop_back();
}
} else if (B == lant[rB].front()) {
for (auto it : lant[rB]) lant[rA].push_front(it);
} else {
while (!lant[rB].empty()) {
lant[rA].push_front(lant[rB].back());
lant[rB].pop_back();
}
}
} else {
///cazul mai naspa in care unesc 2 lanturi
f(A, B, rA, rB);
}
}
}
int CountCritical() {
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
262148 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 |
139 ms |
262144 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 |
157 ms |
262148 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 |
157 ms |
262148 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 |
157 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
