#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 1000005;
int N, glob;
struct dsu {
vector<int> g, sz, deg;
int n, badcnt, allbad, answer;
dsu() {};
dsu (int n, int size) : n(n), answer(size), badcnt(0), allbad(0) {
deg = g = vector<int>(n);
sz = vector<int>(n, 1);
iota(AI(g), 0);
}
int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
void M(int a, int b) {
if (max(++deg[a], ++deg[b]) >= 3) allbad = true;
if (allbad) return;
a = F(a), b = F(b);
if (sz[a] < sz[b]) swap(a, b);
if (a != b) {
return sz[a] += sz[b], g[b] = a, void();
}
if (++badcnt == 2) allbad = true;
// merging into a ring
// which means you have to remove objects on the ring
// all of them is ok, since max deg is 2
// I only care when max deg is <= 2
// and a ring cannot merge with other for max deg <= 2
answer = sz[a];
}
bool noring() { return badcnt == 0 && allbad == false; }
int getans() {
return allbad ? 0 : answer;
}
};
dsu alld, forone;
vector<int> edge[MAX_N];
bool iscan[MAX_N];
vector<int> big, can;
vector<dsu> forcan;
void canpush(int id) { if (iscan[id]) return; iscan[id] = true, can.pb(id); }
void Init(int N_) {
N = N_;
glob = N;
alld = dsu(N, N);
assert(N <= 20000);
// for (int i = 0;i < N;++i)
// adsu[i] = dsu(N, N-1);
}
vector<pair<int,int>> alledge;
// TODO big crisis
// new edge is {a, b}
int over = -1;
void superbig(int id) {
if (over == -1) {
over = id;
forone = dsu(N, N-1);
for (auto [a, b] : alledge)
if (a != id && b != id)
forone.M(a, b);
glob = forone.noring();
}
else if (over != id) {
glob = -1;
return;
}
else {
auto [a, b] = alledge.back();
if (a != id && b != id)
forone.M(a, b);
glob = forone.noring();
}
}
void adjust(int a, int b) {
if (glob == -1) return;
DE(a, b);
if (big.empty()) {
assert(can.empty());
alld.M(a, b);
glob = alld.getans();
return;
}
// pushbig(a), pushbig(b);
//
// if (over != -1) {
// if (a != over && b != over)
// forone.M(a, b);
// glob = forone.getans() == N - 1 ? 1 : -1;
// }
//
// // deal with old ones
// int oldsize = can.size();
// for (int i = 0;i < oldsize;++i) {
// int x = can[i];
// if (a != x && b != x)
// forcan[i].M(a, b);
// }
//
// put new element into candidate
int verybig = 0;
for (int x : big) {
if (edge[x].size() > 3) ++verybig;
canpush(x);
for (int u : edge[x]) canpush(u);
}
if (verybig > 1) {
return glob = -1, void();
}
// examine new candidates
//
// for (int i = oldsize;i < can.size();++i) {
// forcan.pb(N, N-1);
// int x = can[i];
// for (auto [a, b] : alledge) if (a != x && b != x) {
// forcan[i].M(a, b);
// }
// }
// assert(forcan.size() == can.size());
glob = 0;
// // examine all candidates
// for (int i = 0;i < can.size();++i)
// glob += forcan[i].noring();
for (int x : can) {
dsu D(N, N - 1);
for (auto [a, b] : alledge) if (a != x && b != x)
D.M(a, b);
if (D.noring()) ++glob;
}
if (glob == 0) glob = -1;
}
void Link(int A, int B) {
if (glob == -1) return;
edge[A].pb(B), edge[B].pb(A);
if (edge[A].size() == 3) big.pb(A);
if (edge[B].size() == 3) big.pb(B);
if (edge[A].size() > 3) superbig(A);
if (edge[B].size() > 3) superbig(B);
alledge.pb(A, B);
if (over != -1) {
superbig(over);
return;
}
if (big.size() > 4) {
glob = -1;
return;
}
adjust(A, B);
}
int CountCritical() {
if (glob == -1) return 0;
return glob;
}
Compilation message
rings.cpp: In constructor 'dsu::dsu(int, int)':
rings.cpp:25:25: warning: 'dsu::answer' will be initialized after [-Wreorder]
25 | int n, badcnt, allbad, answer;
| ^~~~~~
rings.cpp:25:9: warning: 'int dsu::badcnt' [-Wreorder]
25 | int n, badcnt, allbad, answer;
| ^~~~~~
rings.cpp:28:2: warning: when initialized here [-Wreorder]
28 | dsu (int n, int size) : n(n), answer(size), badcnt(0), allbad(0) {
| ^~~
rings.cpp: In function 'void adjust(int, int)':
rings.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
rings.cpp:113:2: note: in expansion of macro 'DE'
113 | DE(a, b);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
294 ms |
24172 KB |
Output is correct |
| 3 |
Incorrect |
20 ms |
24172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
59 ms |
60524 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
294 ms |
24172 KB |
Output is correct |
| 3 |
Incorrect |
20 ms |
24172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
294 ms |
24172 KB |
Output is correct |
| 3 |
Incorrect |
20 ms |
24172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
294 ms |
24172 KB |
Output is correct |
| 3 |
Incorrect |
20 ms |
24172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
