#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int n;
vector<int> Adj[N];
vector<ii> edges;
int deg[N], mx_deg;
set<ii> se;
int cur_ans = 0;
int szz[N], rtt[N];
void Init(int N_) {
n = N_;
for(int i = 1; i <= n; i++){
szz[i] = 1, rtt[i] = i;
}
cur_ans = n;
}
int cnt;
vector<int> candidates;
int deg2[N][7], mxdeg[7];
bool out[N];
int sz[N][7], rt[N][7];
void init(int ind){
for(int i = 1; i <= n; i++){
sz[i][ind] = 1, rt[i][ind] = i;
deg2[i][ind] = 0;
}
mxdeg[ind] = 0;
out[ind] = 0;
}
int root(int x, int ind){
return (x == rt[x][ind] ? x : rt[x][ind] = root(rt[x][ind], ind));
}
bool merge(int x, int y, int ind){
x = root(x, ind), y = root(y, ind);
if(x == y) return 0;
if(sz[x][ind] < sz[y][ind]) swap(x, y);
sz[x][ind] += sz[y][ind];
rt[y][ind] = x;
return 1;
}
void add_edge(int x, int y, int ind){
if(x == candidates[ind - 1] || y == candidates[ind - 1]) return;
deg2[x][ind]++, deg2[y][ind]++;
mxdeg[ind] = max(mxdeg[ind], deg2[x][ind]);
mxdeg[ind] = max(mxdeg[ind], deg2[y][ind]);
out[ind] |= (!merge(x, y, ind));
out[ind] |= (mxdeg[ind] >= 3);
}
int roott(int x){
return (x == rtt[x] ? x : rtt[x] = roott(rtt[x]));
}
bool mergee(int x, int y){
x = roott(x), y = roott(y);
if(x == y) return 0;
if(szz[x] < szz[y]) swap(x, y);
szz[x] += szz[y];
rtt[y] = x;
return 1;
}
int tol_cyc = 0;
int d[N];
void dfs(int u, int p){
for(auto v : Adj[u]){
if(v == p) continue;
d[v] = d[u] + 1;
dfs(v, u);
}
}
void Link(int A, int B) {
//Adj[A].pb(B);
//Adj[B].pb(A);
edges.pb({A, B});
int old = mx_deg;
se.erase({deg[A], A});
se.erase({deg[B], B});
deg[A]++;
deg[B]++;
se.insert({deg[A], A});
se.insert({deg[B], B});
mx_deg = max(mx_deg, deg[A]);
mx_deg = max(mx_deg, deg[B]);
if(mx_deg <= 2){
int lst = tol_cyc;
tol_cyc += (!mergee(A, B));
if(tol_cyc == 2) cur_ans = 0;
else if(!tol_cyc) cur_ans = n;
else{
if(lst == 1) return;
for(int i = 0; (i + 1) < edges.size(); i++){
Adj[edges[i].fi].pb(edges[i].se);
Adj[edges[i].se].pb(edges[i].fi);
}
dfs(A, A);
cur_ans = d[B] + 1;
}
}
else if(mx_deg == 3){
if(cnt > 4){
cur_ans = 0;
return;
}
if(deg[A] >= 3){
bool ck = 1;
for(auto it : candidates) ck &= (it != A);
if(ck){
cnt++;
init(cnt);
for(auto it : edges) add_edge(it.fi, it.se, cnt);
candidates.pb(A);
}
}
if(deg[B] >= 3){
bool ck = 1;
for(auto it : candidates) ck &= (it != B);
if(ck){
cnt++;
init(cnt);
for(auto it : edges) add_edge(it.fi, it.se, cnt);
candidates.pb(A);
}
}
if(cnt > 4){
cur_ans = 0;
return;
}
for(int i = 1; i <= cnt; i++) add_edge(A, B, i);
cur_ans = 0;
for(int i = 1; i <= cnt; i++) cur_ans += (!out[i]);
}
else{
if(old < 4){
candidates.clear();
cnt = 0;
}
if(deg[A] >= 4){
bool ck = 1;
for(auto it : candidates) ck &= (it != A);
if(ck){
cnt++;
candidates.pb(A);
}
}
if(deg[B] >= 4){
bool ck = 1;
for(auto it : candidates) ck &= (it != B);
if(ck){
cnt++;
candidates.pb(A);
}
}
if(cnt >= 2){
cur_ans = 0;
return;
}
if(old < 4){// build new graph
init(1);
assert(cnt == 1);
for(auto it : edges) add_edge(it.fi, it.se, 1);
}
else{
add_edge(A, B, 1);
}
cur_ans = (!out[1]);
}
}
int CountCritical() {
return cur_ans;
}
Compilation message
rings.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0; (i + 1) < edges.size(); i++){
| ~~~~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
15884 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
14 ms |
21600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
15884 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
15884 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
15884 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
