#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int n, cycsz;
bool nne;
vector<int> adj[1000005];
vector<pair<int, int>> edges;
struct UnionFind1 {
int rt, par[1000005], deg[1000005];
bool vld;
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
void merge(int x, int y) {
if (!vld || x == rt || y == rt) return;
int px = find(x), py = find(y);
if (deg[x] == 2 || deg[y] == 2 || px == py) {
vld = false;
return;
}
deg[x]++;
deg[y]++;
par[find(x)] = find(y);
}
UnionFind1(int root) {
rt = root;
vld = true;
for (int i = 0; i < 1000005; i++) {
par[i] = i;
deg[i] = 0;
}
for (auto [a, b] : edges) {
merge(a, b);
}
}
};
struct UnionFind2 {
int par[1000005], sz[1000005];
UnionFind2() {
for (int i = 0; i < 1000005; i++) {
par[i] = i;
sz[i] = 1;
}
}
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
sz[x] += sz[y];
par[y] = x;
return true;
}
} cyc;
vector<UnionFind1> uf;
void Init(int N) {
n = N;
}
int CountCritical() {
if (nne) return 0;
if (!uf.empty()) {
int ans = 0;
for (int i = 0; i < uf.size(); i++) {
ans += uf[i].vld;
}
return ans;
} else if (cycsz) return cycsz;
return n;
}
void Link(int a, int b) {
if (nne) return;
if (!uf.empty()) {
for (int i = 0; i < uf.size(); i++) {
uf[i].merge(a, b);
}
return;
}
edges.push_back({a, b});
adj[a].push_back(b);
adj[b].push_back(a);
if (adj[a].size() < adj[b].size()) swap(a, b);
if (adj[a].size() == 3) {
uf.push_back(UnionFind1(a));
for (int i : adj[a]) {
uf.push_back(UnionFind1(i));
}
return;
}
if (!cyc.merge(a, b)) {
if (cycsz) {
nne = true;
return;
}
cycsz = cyc.sz[cyc.find(a)];
}
}
Compilation message
rings.cpp: In function 'int CountCritical()':
rings.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UnionFind1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < uf.size(); i++) {
| ~~^~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UnionFind1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < uf.size(); i++) {
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39380 KB |
Output is correct |
2 |
Correct |
185 ms |
78704 KB |
Output is correct |
3 |
Correct |
233 ms |
78640 KB |
Output is correct |
4 |
Correct |
57 ms |
39476 KB |
Output is correct |
5 |
Correct |
132 ms |
39592 KB |
Output is correct |
6 |
Correct |
215 ms |
39732 KB |
Output is correct |
7 |
Correct |
65 ms |
78528 KB |
Output is correct |
8 |
Correct |
158 ms |
39704 KB |
Output is correct |
9 |
Correct |
224 ms |
78788 KB |
Output is correct |
10 |
Correct |
226 ms |
78816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4053 ms |
45332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39380 KB |
Output is correct |
2 |
Correct |
185 ms |
78704 KB |
Output is correct |
3 |
Correct |
233 ms |
78640 KB |
Output is correct |
4 |
Correct |
57 ms |
39476 KB |
Output is correct |
5 |
Correct |
132 ms |
39592 KB |
Output is correct |
6 |
Correct |
215 ms |
39732 KB |
Output is correct |
7 |
Correct |
65 ms |
78528 KB |
Output is correct |
8 |
Correct |
158 ms |
39704 KB |
Output is correct |
9 |
Correct |
224 ms |
78788 KB |
Output is correct |
10 |
Correct |
226 ms |
78816 KB |
Output is correct |
11 |
Correct |
248 ms |
78704 KB |
Output is correct |
12 |
Correct |
390 ms |
79080 KB |
Output is correct |
13 |
Correct |
415 ms |
78900 KB |
Output is correct |
14 |
Correct |
293 ms |
78664 KB |
Output is correct |
15 |
Correct |
284 ms |
78628 KB |
Output is correct |
16 |
Correct |
394 ms |
40076 KB |
Output is correct |
17 |
Correct |
427 ms |
78808 KB |
Output is correct |
18 |
Correct |
422 ms |
78788 KB |
Output is correct |
19 |
Correct |
388 ms |
39932 KB |
Output is correct |
20 |
Correct |
423 ms |
79028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39380 KB |
Output is correct |
2 |
Correct |
185 ms |
78704 KB |
Output is correct |
3 |
Correct |
233 ms |
78640 KB |
Output is correct |
4 |
Correct |
57 ms |
39476 KB |
Output is correct |
5 |
Correct |
132 ms |
39592 KB |
Output is correct |
6 |
Correct |
215 ms |
39732 KB |
Output is correct |
7 |
Correct |
65 ms |
78528 KB |
Output is correct |
8 |
Correct |
158 ms |
39704 KB |
Output is correct |
9 |
Correct |
224 ms |
78788 KB |
Output is correct |
10 |
Correct |
226 ms |
78816 KB |
Output is correct |
11 |
Correct |
248 ms |
78704 KB |
Output is correct |
12 |
Correct |
390 ms |
79080 KB |
Output is correct |
13 |
Correct |
415 ms |
78900 KB |
Output is correct |
14 |
Correct |
293 ms |
78664 KB |
Output is correct |
15 |
Correct |
284 ms |
78628 KB |
Output is correct |
16 |
Correct |
394 ms |
40076 KB |
Output is correct |
17 |
Correct |
427 ms |
78808 KB |
Output is correct |
18 |
Correct |
422 ms |
78788 KB |
Output is correct |
19 |
Correct |
388 ms |
39932 KB |
Output is correct |
20 |
Correct |
423 ms |
79028 KB |
Output is correct |
21 |
Correct |
990 ms |
40984 KB |
Output is correct |
22 |
Correct |
1569 ms |
41852 KB |
Output is correct |
23 |
Correct |
1959 ms |
42904 KB |
Output is correct |
24 |
Correct |
1659 ms |
78868 KB |
Output is correct |
25 |
Correct |
340 ms |
78852 KB |
Output is correct |
26 |
Correct |
2473 ms |
78936 KB |
Output is correct |
27 |
Correct |
3164 ms |
43796 KB |
Output is correct |
28 |
Correct |
3117 ms |
78916 KB |
Output is correct |
29 |
Correct |
1172 ms |
78984 KB |
Output is correct |
30 |
Correct |
3735 ms |
44692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39380 KB |
Output is correct |
2 |
Correct |
185 ms |
78704 KB |
Output is correct |
3 |
Correct |
233 ms |
78640 KB |
Output is correct |
4 |
Correct |
57 ms |
39476 KB |
Output is correct |
5 |
Correct |
132 ms |
39592 KB |
Output is correct |
6 |
Correct |
215 ms |
39732 KB |
Output is correct |
7 |
Correct |
65 ms |
78528 KB |
Output is correct |
8 |
Correct |
158 ms |
39704 KB |
Output is correct |
9 |
Correct |
224 ms |
78788 KB |
Output is correct |
10 |
Correct |
226 ms |
78816 KB |
Output is correct |
11 |
Execution timed out |
4053 ms |
45332 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |