#include<cstdio>
#include<vector>
using namespace std;
const int SZ = 1000010;
int min(int a, int b) { return a < b ? a : b; }
int n;
const bool ifDebug = false;
int cycleNum;
vector<int>l[SZ];
typedef struct Graph {
int st[4], ts[3];
int p[SZ], sz[SZ], ln[SZ], c[SZ];
bool is3E[SZ];
int x;
bool isMain;
void init() {
x = n;
isMain = true;
st[0] = ts[0] = n;
st[1] = st[2] = st[3] = ts[1] = ts[2] = 0;
for (int i = 0; i < n; i++) {
p[i] = i;
sz[i] = 1;
ln[i] = c[i] = 0;
is3E[i] = false;
}
}
void init(int X) {
if (ifDebug)printf("init(%d)\n", X);
init();
isMain = false;
x = X;
PR();
for (int i = 0; i < n; i++) {
for (int e : l[i]) {
if (e < i)Link(e, i);
}
}
}
int f(int a) {
return a == p[a] ? a : p[a] = f(p[a]);
}
void u(int A, int B) {
int a = f(A), b = f(B);
if (a != b) {
p[b] = a;
ts[gT(a)]--;
ts[gT(b)]--;
ln[a] += ln[b];
sz[a] += sz[b];
}
else {
ts[gT(a)]--;
}
}
void Con(int A, int B) {
int a = f(A);
st[min(c[A], 3)]--;
if (isMain)l[A].push_back(B);
c[A]++;
st[min(c[A], 3)]++;
if (c[A] >= 3)is3E[a] = true;
}
int gT(int a) {
if (is3E[a]) {
return 2;
}
else if (sz[a] == ln[a]) {
return 1;
}
else {
return 0;
}
}
void Link(int A, int B) {
if (A == x || B == x)return;
if (ifDebug)printf("%d:%d-%d\n", x, A, B);
u(A, B);
Con(A, B);
Con(B, A);
int a = f(A);
ln[a]++;
ts[gT(a)]++;
}
bool isChain() {
return (ts[1] + ts[2] == 0);
}
void PR() {
if (!ifDebug)return;
printf("-------%d-------\n", x);
for (int a = 0; a < n; a++) {
printf("(%d)", c[a]);
if (a == p[a]) {
printf("[%d(%d,%d,%d)]", a, sz[a], gT(a),ln[a]);
printf("\n");
}
else {
printf("%d->%d\n", a, f(a));
}
}
printf("-----------------\n");
}
}Graph;
Graph MG;
vector<Graph>GV;
//type: 0-chain/1-cycle/2-3 exists/3-4 exists
void Init(int N) {
cycleNum = n = N;
MG.init();
}
void Link(int A, int B) {
bool p = (MG.st[3] == 0);
MG.Link(A, B);
for (int i = 0; i < GV.size(); i++) {
GV[i].Link(A, B);
}
if (MG.gT(MG.f(A)) == 1)cycleNum = MG.f(A);
if (MG.gT(MG.f(B)) == 1)cycleNum = MG.f(B);
if (p && MG.st[3]) {
int a = A;
if (l[A].size() < 3)a = B;
GV.resize(l[a].size() + 1);
GV[l[a].size()].init(a);
for (int i = 0; i < l[a].size(); i++) {
GV[i].init(l[a][i]);
}
}
}
int CountCritical() {
if (MG.ts[2]) {
if (ifDebug)printf(">=3 Exists");
int r = 0;
for (int i = 0; i < GV.size(); i++) {
if (GV[i].isChain())r++;
}
return r;
}
else if (MG.ts[1]) {
if (ifDebug)printf("cycle Exists");
if (MG.ts[1] > 1)return 0;
return MG.sz[cycleNum];
}
else {
if (ifDebug)printf("Already Chain");
return n;
}
}
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Graph>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i = 0; i < GV.size(); i++) {
| ~~^~~~~~~~~~~
rings.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < l[a].size(); i++) {
| ~~^~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Graph>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < GV.size(); i++) {
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
107204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
449 ms |
55580 KB |
Output is correct |
| 2 |
Incorrect |
2292 ms |
155884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
107204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
107204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
107204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
