#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000005;
vector<int> gr[NMAX];
struct chainsdsu{
int dad;
int l, r;
int sz;
bool iscycle;
};
int other(int x, int a1, int a2){ /// cel care nu e egal cu x, daca ambele sunt egale x
if(x == a1)
return a2;
return a1;
}
struct chainDS{ /// pentru variantele care accepta doar lanturi => cand answer devine mic (leg lant de lant de necapete, leg un ciclu in interior, leg lant de ciclu)
///variante cand nu merge deloc : mai mult de un ciclu
vector<chainsdsu> d;
int N;
bool ans;
chainDS(int sz) : d(sz + 1), N(sz){
for(int i = 1; i<= N; i++){
d[i] = {i, i, i, 1, false};
}
ans = true;
}
int findd(int x){
if(d[x].dad == x)
return x;
return d[x].dad = findd(d[x].dad);
}
bool AddEdge(int x, int y){
int dx = findd(x);
int dy = findd(y);
if(dx == dy){
ans = false;
return ans;
}
if(!((x == d[dx].l || x == d[dx].r) && (y == d[dy].l || y == d[dy].r))){
ans = false;
return ans;
}
if(d[dx].sz < d[dy].sz){
swap(dx, dy);
swap(x, y);
}
d[dy].dad = dx;
d[dx].l = other(x, d[dx].l, d[dx].r);
d[dx].r = other(y, d[dy].l, d[dy].r);
d[dx].sz += d[dy].sz;
return ans;
}
};
vector<pair<int, chainDS>> pos; /// nodurile ramase posibile
vector<pair<int, int>> edges;
chainsdsu d[NMAX];
int findd(int x){
if(x == d[x].dad)
return x;
return d[x].dad = findd(d[x].dad);
}
int N;
int nrcycle = 0;
int cans = 0;
void Init(int N_) {
N = N_;
for(int i = 1; i<= N; i++){
d[i] = {i, i, i, 1, false};
gr[i].clear();
}
pos.clear();
edges.clear();
nrcycle = 0;
cans = N;
}
void makepos(int A, int B){
unordered_set<int> vec;
for(auto x: gr[A])
vec.insert(x);
for(auto x: gr[B])
vec.insert(x);
for(auto x: vec){
pos.push_back({x, chainDS(N)});
for(auto e:edges){
if(e.first != x && e.second != x){
pos.back().second.AddEdge(e.first, e.second);
}
}
}
}
void Link(int A, int B) {
A++;
B++;
if(pos.size()){
for(auto &x:pos){
if(x.first != A && x.first != B)
x.second.AddEdge(A, B);
}
return;
}
gr[A].push_back(B);
gr[B].push_back(A);
edges.push_back({A, B});
chainsdsu &dA = d[findd(A)];
chainsdsu &dB = d[findd(B)];
if(dA.dad != dB.dad){
/// cazul in care leg doua lanturi (bine sau gresit) sau un ciclu cu un lant
if(dA.sz < dB.sz){
swap(dA, dB);
swap(A, B);
}
if(dA.iscycle == false && dB.iscycle == false && (A == dA.l || A == dA.r) && (B == dB.l || B == dB.r)){
/// cazul ok
dB.dad = dA.dad;
dA.sz += dB.sz;
dA.l = other(A, dA.l, dA.r);
dA.r = other(B, dB.l, dB.r);
return;
}
/// stric ceva deci trebuie sa repar
makepos(A, B);
}
else{
/// cazul in care creez un ciclu
if(dA.iscycle == false)
nrcycle++;
if((A == dA.l && B == dA.r) || (A == dA.r && B == dA.l)){
/// ciclu simplu
dA.iscycle = true;
cans = dA.sz;
return;
}
/// stric ceva deci trb sa fortez poz optime
makepos(A, B);
}
}
int CountCritical() {
if(pos.size()){
int ans = 0;
for(auto &x:pos){
if(x.second.ans == true)
ans++;
}
return ans;
}
if(nrcycle > 1)
return 0;
return cans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
24108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
54280 KB |
Output is correct |
| 2 |
Incorrect |
744 ms |
86852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
24108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
24108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
24108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
