#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> edg[1000005];
int DEG3 = -1;
int DEG4 = -1;
bool choicesToggle = false;
set<int> choices;
int dsu[1000005];
int cyc[1000005];
bool vis[1000005];
int pre[1000005];
int GG = 0;
int find(int x) {
if(dsu[x]==x)return x;
return dsu[x] = find(dsu[x]);
}
void setintersection(set<int> tmp) {
if(!choicesToggle) {
choicesToggle = true;
choices = tmp;
return;
}
set<int> tmp2;
for(int i:tmp) {
if(choices.find(i)!=choices.end()) {
tmp2.insert(i);
}
}
choices = tmp2;
}
void dfs(int x, int p, int tar) {
vis[x] = true;
pre[x] = p;
if(x==tar) {
int ptr = tar;
set<int> tmp;
while(ptr != -1) {
tmp.insert(ptr);
ptr = pre[ptr];
}
setintersection(tmp);
return;
}
for(int i:edg[x]) {
if(i==p) continue;
dfs(i, x, tar);
}
}
void merge(int x, int y) {
if(find(x)==find(y)) {
if(cyc[find(x)]) GG = 1;
cyc[find(x)] = true;
dfs(x, -1, y);
} else {
if(cyc[find(y)]) cyc[find(x)] = true;
dsu[find(y)] = find(x);
}
}
void Init(int N_) {
N = N_;
for(int i=0; i<N; i++) dsu[i] = i;
}
void Link(int A, int B) {
merge(A, B);
edg[A].push_back(B);
edg[B].push_back(A);
if(edg[A].size()==4) setintersection({A});
else if(edg[A].size()==3) setintersection({A, edg[A][0], edg[A][1], edg[A][2]});
if(edg[B].size()==4) setintersection({B});
else if(edg[B].size()==3) setintersection({B, edg[B][0], edg[B][1], edg[B][2]});
}
int CountCritical() {
if(GG) return 0;
if(!choicesToggle) return N;
else return choices.size();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24404 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25204 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
16 ms |
24204 KB |
Output is correct |
| 9 |
Correct |
16 ms |
24020 KB |
Output is correct |
| 10 |
Correct |
18 ms |
24044 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
332 ms |
46200 KB |
Output is correct |
| 2 |
Correct |
671 ms |
56012 KB |
Output is correct |
| 3 |
Execution timed out |
4083 ms |
182928 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24404 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25204 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
16 ms |
24204 KB |
Output is correct |
| 9 |
Correct |
16 ms |
24020 KB |
Output is correct |
| 10 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 11 |
Runtime error |
478 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24404 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25204 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
16 ms |
24204 KB |
Output is correct |
| 9 |
Correct |
16 ms |
24020 KB |
Output is correct |
| 10 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 11 |
Runtime error |
478 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24404 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25204 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
16 ms |
24204 KB |
Output is correct |
| 9 |
Correct |
16 ms |
24020 KB |
Output is correct |
| 10 |
Correct |
18 ms |
24044 KB |
Output is correct |
| 11 |
Correct |
332 ms |
46200 KB |
Output is correct |
| 12 |
Correct |
671 ms |
56012 KB |
Output is correct |
| 13 |
Execution timed out |
4083 ms |
182928 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
