#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
const int N = 100000 + 5;
int n, sz = 0, h[N];
int cycle[7], rem[7], stop = 0, p[N][7];
set<pii> tried[5], deg;
vector<int> V[7][N];
void Init(int N_) {
n = N_;
for(int i = 0; i < n; i++) {
for(int t = 0; t < 6; t++) {
p[i][t] = i;
}
deg.insert({0, i});
}
}
int find(int a, int t) {
return (p[a][t] == a ? p[a][t] : p[a][t] = find(p[a][t], t));
}
void merge(int a,int b, int t) {
a = find(a, t); b = find(b, t);
if(a == b) return;
p[a][t] = b;
return;
}
void dfs(int a, int p) {
h[a] = h[p] + 1;
for(int i = 0; i < V[5][a].size(); i++) {
if(V[5][a][i] == p) continue;
if(h[V[5][a][i]]) {
sz = h[a] - h[V[5][a][i]] + 1;
return;
}
}
}
void add(int a, int b, int t) {
if(a == rem[t] || b == rem[t]) return;
tried[t].erase({V[t][a].size(), a});
tried[t].erase({V[t][b].size(), b});
V[t][a].push_back(b); V[t][b].push_back(a);
tried[t].insert({V[t][a].size(), a});
tried[t].insert({V[t][b].size(), b});
if(find(a, t) == find(b, t)) cycle[t] = 1;
else merge(a, b, t);
return;
}
void Link(int a, int b) {
deg.erase({V[5][a].size(), a});
deg.erase({V[5][b].size(), b});
V[5][a].push_back(b); V[5][b].push_back(a);
deg.insert({V[5][a].size(), a});
deg.insert({V[5][b].size(), b});
if(find(a, 5) != find(b, 5)) {
merge(a, b, 5);
}
else {
if(!cycle[5]) {
merge(a, b, 5);
dfs(a, -1);
cycle[5] = a + 1;
}
else if(find(a, 5) != find(cycle[5] - 1, 5)) {
stop = 1;
}
}
if(tried[0].size()) {
add(a, b, 0);
}
if(tried[1].size()) {
for(int i = 1; i <= 4; i++) add(a, b, i);
}
}
void build(int t) {
int u = rem[t];
for(int i = 0; i < n; i++) {
if(u == i) continue;
for(int j = 0; j < V[5][i].size(); j++) {
int v = V[5][i][j];
if(v == u || v < i) continue;
if(find(v, t) == find(i, t)) cycle[t] = 1;
merge(i, v, t);
V[t][i].push_back(v); V[t][v].push_back(i);
}
}
for(int i = 0; i < n; i++) tried[t].insert({V[t][i].size(), i});
}
int CountCritical() {
if(stop) return 0;
if(!cycle[5] && (*--deg.end()).f <= 2) return n;
if((*--deg.end()).f <= 2) return sz;
if((*--deg.end()).f >= 4) {
if(!tried[0].size()) {
rem[0] = (*--deg.end()).s;
build(0);
}
if((*--tried[0].end()).f <= 2 && !cycle[0]) return 1;
stop = 1;
return 0;
}
if(!tried[1].size()) {
rem[1] = (*--deg.end()).s;
for(int i = 0; i < V[5][rem[1]].size(); i++) {
rem[i + 2] = V[5][rem[1]][i];
}
for(int i = 1; i <= 4; i++) {
build(i);
}
}
int cn = 0;
for(int i = 1; i <= 4; i++) {
if((*--tried[i].end()).f <= 2 && !cycle[i]) cn++;
}
return cn;
}
Compilation message
rings.cpp: In function 'void dfs(int, int)':
rings.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < V[5][a].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void build(int)':
rings.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int j = 0; j < V[5][i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0; i < V[5][rem[1]].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
16728 KB |
Output is correct |
| 2 |
Correct |
15 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
17 ms |
17692 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
16852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
54 ms |
51292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
16728 KB |
Output is correct |
| 2 |
Correct |
15 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
17 ms |
17692 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
16852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
16728 KB |
Output is correct |
| 2 |
Correct |
15 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
17 ms |
17692 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
16852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
16728 KB |
Output is correct |
| 2 |
Correct |
15 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
17 ms |
17692 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
16852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
