#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> graph[1000005];
int n;
struct disj{
int pa[1000005];
int degcnt[1000005][5];
int repres3[1000005];
int repres4[1000005];
int cnt[1000005];
int size[1000005];
void init(int n){
for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, size[i] = 1, repres3[i] = repres4[i] = -1;
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
void uni(int p, int q){
p = find(p); q = find(q);
if(p == q) return;
pa[q] = p; find(q);
for(int i=0; i<5; i++){
degcnt[p][i] += degcnt[q][i];
}
size[p] += size[q];
repres4[p] = max(repres4[p], repres4[q]);
repres3[p] = max(repres3[p], repres3[q]);
}
}disj;
void Init(int N){
n = N;
disj.init(n);
}
int deg[1000005];
int focus = -1;
bool deadend = 0;
void Link(int A, int B){
graph[A].push_back(B);
graph[B].push_back(A);
deg[A]++, deg[B]++;
int p = disj.find(A);
if(deg[A] <= 4){
disj.degcnt[p][deg[A]-1]--;
disj.degcnt[p][deg[A]]++;
if(deg[A] == 3) disj.repres3[p] = A;
if(deg[A] == 4) disj.repres4[p] = A;
}
p = disj.find(B);
if(deg[B] <= 4){
disj.degcnt[p][deg[B]-1]--;
disj.degcnt[p][deg[B]]++;
if(deg[B] == 3) disj.repres3[p] = B;
if(deg[B] == 4) disj.repres4[p] = B;
}
disj.uni(A,B);
p = disj.find(A);
if(disj.degcnt[p][3] || disj.degcnt[p][4] || (disj.degcnt[p][2] == disj.size[2])){
if(focus == -1) focus = p;
else{
focus = disj.find(focus);
if(focus != p){
deadend = 1;
}
}
}
}
bool vis[1000005];
queue<int> q;
bool tvis[1000005];
int solve(int x){
memset(tvis,0,sizeof(tvis));
tvis[x] = 1;
int ret = 1;
for(auto &i : graph[x]){
deg[x]--;
deg[i]--;
}
for(auto &i : graph[x]){
if(tvis[i]) continue;
tvis[i] = 1;
q.push(i);
int foundThree = 0, foundOne = 0, foundTwo = 0;
while(!q.empty()){
int qf = q.front();
q.pop();
if(deg[qf] >= 3) foundThree = 1;
if(deg[qf] == 1) foundOne = 1;
if(deg[qf] == 2) foundTwo = 1;
for(auto &i : graph[qf]){
if(!tvis[i]){
tvis[i] = 1;
q.push(i);
}
}
}
if(foundThree == 1){
ret = 0;
break;
}
if(foundTwo && !foundOne){
ret = 0;
break;
}
}
for(auto &i : graph[x]){
deg[x]++;
deg[i]++;
}
return ret;
}
int CountCritical(){
if(focus == -1) return n;
if(deadend == 1) return 0;
memset(vis,0,sizeof(vis));
int ret = 0;
if(disj.degcnt[focus][2] == disj.size[focus]){
return disj.size[focus];
}
if(disj.degcnt[focus][4] == 1){
return solve(disj.repres4[focus]);
}
int p = disj.repres3[focus];
ret = solve(p);
for(auto &i : graph[p]){
if(solve(i)) ret++;
}
return ret;
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
void Init(int N);
int CountCritical();
void Link(int a, int b);
int main() {
int tmp;
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
int N, L;
tmp = scanf("%d %d", &N, &L);
assert(tmp == 2);
Init(N);
int i;
for (i = 0; i < L; i++) {
int A, B;
tmp = scanf("%d", &A);
if (A == -1) {
int critical;
critical = CountCritical();
printf("%d\n", critical);
} else {
tmp = scanf("%d", &B);
assert(tmp == 1);
Link(A, B);
}
}
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
639 ms |
60652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
