#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int MAX = 1000005;
struct DSU {
vi e;
DSU(int N) {
e = vi(N, -1);
}
int root(int x) {
if (e[x] < 0) {
return x;
}
else {
e[x] = root(e[x]);
return e[x];
}
}
bool sameset(int x, int y) {
return (root(x) == root(y));
}
bool unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y)
return false;
if (-e[x] < -e[y])
swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
int size(int x) {
return -e[root(x)];
}
};
int N;
vi adj[MAX];
void Init(int N_) {
N = N_;
}
void Link(int A, int B) {
adj[A].pb(B);
adj[B].pb(A);
}
int CountCritical() {
vi sus;
for (int i = 0; i < N; i++) {
if (adj[i].size() >= 3) {
sus.pb(i);
if (adj[i].size() == 3) {
for (int x : adj[i])
sus.pb(x);
}
break;
}
}
if ((int)(sus.size()) > 0) {
int total = 0;
for (int i : sus) {
// try removing each vertex, make new adj
// to check, ensure no adj cnt is > 2
// and N - edge_cnt equals number of ccs
// removed link is a chain itself
vi adjc[N];
int cnt = 0;
for (int j = 0; j < N; j++) {
if (j == i)
continue;
for (int k : adj[j]) {
if (k != i) {
adjc[j].pb(k);
cnt++;
}
}
}
cnt /= 2;
int maxc = 0;
for (int j = 0; j < N; j++) {
maxc = max(maxc, (int)(adjc[j].size()));
}
// cout<<"cnt, maxc: "<<cnt<<" "<<maxc<<endl;
int ccs = 0;
vector<bool> vis(N, false);
for (int j = 0; j < N; j++) {
if (!vis[j]) {
ccs++;
queue<int> q;
q.push(j);
vis[j] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : adjc[x]) {
if (!vis[y]) {
q.push(y);
vis[y] = true;
}
}
}
}
}
// cout<<"ccs: "<<ccs<<endl;
if ((maxc <= 2) && (N - cnt == ccs))
total++;
}
return total;
}
else { // all vertices have degree <= 2
// all lines or cycles
int cnt = 0;
for (int j = 0; j < N; j++) {
cnt += (int)(adj[j].size());
}
cnt /= 2;
int ccs = 0;
vector<bool> vis(N, false);
for (int j = 0; j < N; j++) {
if (!vis[j]) {
ccs++;
queue<int> q;
q.push(j);
vis[j] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : adj[x]) {
if (!vis[y]) {
q.push(y);
vis[y] = true;
}
}
}
}
}
if (N - cnt == ccs) {
return N;
}
else if (N - cnt == ccs - 1) { // one cycle, find length
// given adjacency list, find the cycle
// find all components, then find # edges in comp
DSU dsu(N);
for (int i = 0; i < N; i++) {
for (int j : adj[i])
dsu.unite(i, j);
}
vector<vi> incomp(N); // N vectors
for (int i = 0; i < N; i++) {
incomp[dsu.root(i)].pb(i);
}
int ans = -1;
for (int i = 0; i < N; i++) {
if ((int)(incomp[i].size()) != 0) {
int sumd = 0;
for (int j : incomp[i])
sumd += (int)(adj[j].size());
if (sumd / 2 == (int)(incomp[i].size())) {
ans = sumd / 2;
break;
}
}
}
return ans;
}
else {
return 0;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23900 KB |
Output is correct |
2 |
Correct |
13 ms |
24352 KB |
Output is correct |
3 |
Correct |
13 ms |
24412 KB |
Output is correct |
4 |
Correct |
12 ms |
24008 KB |
Output is correct |
5 |
Correct |
11 ms |
24156 KB |
Output is correct |
6 |
Correct |
12 ms |
24156 KB |
Output is correct |
7 |
Correct |
12 ms |
23984 KB |
Output is correct |
8 |
Correct |
12 ms |
23900 KB |
Output is correct |
9 |
Correct |
15 ms |
24184 KB |
Output is correct |
10 |
Correct |
13 ms |
24412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
46932 KB |
Output is correct |
2 |
Correct |
559 ms |
103248 KB |
Output is correct |
3 |
Correct |
1072 ms |
115148 KB |
Output is correct |
4 |
Correct |
705 ms |
101712 KB |
Output is correct |
5 |
Correct |
701 ms |
101456 KB |
Output is correct |
6 |
Correct |
665 ms |
99524 KB |
Output is correct |
7 |
Correct |
584 ms |
113488 KB |
Output is correct |
8 |
Correct |
1682 ms |
116872 KB |
Output is correct |
9 |
Correct |
1823 ms |
123304 KB |
Output is correct |
10 |
Correct |
459 ms |
66208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23900 KB |
Output is correct |
2 |
Correct |
13 ms |
24352 KB |
Output is correct |
3 |
Correct |
13 ms |
24412 KB |
Output is correct |
4 |
Correct |
12 ms |
24008 KB |
Output is correct |
5 |
Correct |
11 ms |
24156 KB |
Output is correct |
6 |
Correct |
12 ms |
24156 KB |
Output is correct |
7 |
Correct |
12 ms |
23984 KB |
Output is correct |
8 |
Correct |
12 ms |
23900 KB |
Output is correct |
9 |
Correct |
15 ms |
24184 KB |
Output is correct |
10 |
Correct |
13 ms |
24412 KB |
Output is correct |
11 |
Correct |
64 ms |
24400 KB |
Output is correct |
12 |
Correct |
52 ms |
24936 KB |
Output is correct |
13 |
Correct |
151 ms |
24652 KB |
Output is correct |
14 |
Correct |
145 ms |
24544 KB |
Output is correct |
15 |
Correct |
248 ms |
24616 KB |
Output is correct |
16 |
Correct |
39 ms |
24556 KB |
Output is correct |
17 |
Correct |
200 ms |
24660 KB |
Output is correct |
18 |
Correct |
341 ms |
25200 KB |
Output is correct |
19 |
Correct |
37 ms |
24656 KB |
Output is correct |
20 |
Correct |
120 ms |
24868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23900 KB |
Output is correct |
2 |
Correct |
13 ms |
24352 KB |
Output is correct |
3 |
Correct |
13 ms |
24412 KB |
Output is correct |
4 |
Correct |
12 ms |
24008 KB |
Output is correct |
5 |
Correct |
11 ms |
24156 KB |
Output is correct |
6 |
Correct |
12 ms |
24156 KB |
Output is correct |
7 |
Correct |
12 ms |
23984 KB |
Output is correct |
8 |
Correct |
12 ms |
23900 KB |
Output is correct |
9 |
Correct |
15 ms |
24184 KB |
Output is correct |
10 |
Correct |
13 ms |
24412 KB |
Output is correct |
11 |
Correct |
64 ms |
24400 KB |
Output is correct |
12 |
Correct |
52 ms |
24936 KB |
Output is correct |
13 |
Correct |
151 ms |
24652 KB |
Output is correct |
14 |
Correct |
145 ms |
24544 KB |
Output is correct |
15 |
Correct |
248 ms |
24616 KB |
Output is correct |
16 |
Correct |
39 ms |
24556 KB |
Output is correct |
17 |
Correct |
200 ms |
24660 KB |
Output is correct |
18 |
Correct |
341 ms |
25200 KB |
Output is correct |
19 |
Correct |
37 ms |
24656 KB |
Output is correct |
20 |
Correct |
120 ms |
24868 KB |
Output is correct |
21 |
Execution timed out |
4040 ms |
24100 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23900 KB |
Output is correct |
2 |
Correct |
13 ms |
24352 KB |
Output is correct |
3 |
Correct |
13 ms |
24412 KB |
Output is correct |
4 |
Correct |
12 ms |
24008 KB |
Output is correct |
5 |
Correct |
11 ms |
24156 KB |
Output is correct |
6 |
Correct |
12 ms |
24156 KB |
Output is correct |
7 |
Correct |
12 ms |
23984 KB |
Output is correct |
8 |
Correct |
12 ms |
23900 KB |
Output is correct |
9 |
Correct |
15 ms |
24184 KB |
Output is correct |
10 |
Correct |
13 ms |
24412 KB |
Output is correct |
11 |
Correct |
189 ms |
46932 KB |
Output is correct |
12 |
Correct |
559 ms |
103248 KB |
Output is correct |
13 |
Correct |
1072 ms |
115148 KB |
Output is correct |
14 |
Correct |
705 ms |
101712 KB |
Output is correct |
15 |
Correct |
701 ms |
101456 KB |
Output is correct |
16 |
Correct |
665 ms |
99524 KB |
Output is correct |
17 |
Correct |
584 ms |
113488 KB |
Output is correct |
18 |
Correct |
1682 ms |
116872 KB |
Output is correct |
19 |
Correct |
1823 ms |
123304 KB |
Output is correct |
20 |
Correct |
459 ms |
66208 KB |
Output is correct |
21 |
Correct |
64 ms |
24400 KB |
Output is correct |
22 |
Correct |
52 ms |
24936 KB |
Output is correct |
23 |
Correct |
151 ms |
24652 KB |
Output is correct |
24 |
Correct |
145 ms |
24544 KB |
Output is correct |
25 |
Correct |
248 ms |
24616 KB |
Output is correct |
26 |
Correct |
39 ms |
24556 KB |
Output is correct |
27 |
Correct |
200 ms |
24660 KB |
Output is correct |
28 |
Correct |
341 ms |
25200 KB |
Output is correct |
29 |
Correct |
37 ms |
24656 KB |
Output is correct |
30 |
Correct |
120 ms |
24868 KB |
Output is correct |
31 |
Execution timed out |
4040 ms |
24100 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |