#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n , comp[N], mx , adj[N] , ans = 0 , cycles = 0 , vis[N] , vi = 0 , comp2[4][N] , con1[4][N] , con2[4][N];
vector< int > g[N];
vector< pair<int,bool> > v;
int Find(int u){
return (u == comp[u] ? u : comp[u] = Find(comp[u]));
}
int Find2(int u,int i){
if(u == comp2[i][u])
return u;
return comp2[i][u] = Find2(comp2[i][u],i);
}
void Init(int N_) {
n = N_;
ans = n ;
for(int i=0;i<n;i++)
comp[i] = i;
mx = 0 ;
cycles = 0 ;
}
void DFS(int node,int prnt,int last){
ans++;
if(node == last) return;
for(int i=0;i<(int)g[node].size();i++){
if(g[node][i] != prnt) DFS(g[node][i],node,last);
}
}
void DFS2(int node,int cant,vector< pair<int,int> > &v){
vis[node] = vi;
int num = 0 ;
for(int i=0;i<(int)g[node].size();i++){
int newnode = g[node][i];
num += (newnode != cant);
if(vis[newnode] == vi || newnode == cant) continue;
DFS2(newnode,cant,v);
}
v.push_back(make_pair(node,num));
}
void make(int u){
v.push_back(make_pair(u,true));
for(int i=0;i<(int)g[u].size();i++){
v.push_back(make_pair(g[u][i],true));
}
ans = 0 ;
vector< pair<int,int> > v2;
for(int i=0;i<(int)v.size();i++){
vi++;
int cnt = 0 ;
for(int j=0;j<n;j++){
if(j == v[i].first || vis[j] == vi) continue;
v2.clear();
cnt = j;
DFS2(j,v[i].first,v2);
if(v2.size() == 1){
con1[i][cnt] = con2[i][cnt] = v2[0].first;
}
else if(v2.size() == 2){
con1[i][cnt] = v2[0].first;
con2[i][cnt] = v2[1].first;
}
else{
vector<int> tmp;
for(int i=0;i<(int)v2.size();i++){
if(v2[i].second == 1){
tmp.push_back(v2[i].first);
}
}
if(tmp.size() < 2){
v[i].second = false;
break;
}
else{
con1[i][cnt] = tmp[0];
con2[i][cnt] = tmp[1];
}
}
for(int k=0;k<(int)v2.size();k++){
comp2[i][v2[k].first] = cnt;
}
}
ans += v[i].second;
}
}
void Link(int a, int b) {
if(ans == 0) return;
if(mx < 3){
int u = Find(a);
int v = Find(b);
adj[a]++;
adj[b]++;
g[a].push_back(b);
g[b].push_back(a);
if(adj[a] == 3){
mx = 3;
make(a);
return ;
}
if(adj[b] == 3){
mx = 3;
make(b);
return;
}
if(u == v){
if(cycles > 0){
ans = 0;
return ;
}
cycles++;
ans = 0 ;
DFS(a,b,b);
}
else{
comp[u] = v;
}
return ;
}
for(int i=0;i<(int)v.size();i++){
if(v[i].second == false || v[i].first == a || v[i].first == b) continue;
int u = Find2(comp2[i][a],i);
int vv = Find2(comp2[i][b],i);
if(u == vv){
v[i].second = false;
continue;
}
if(a != con1[i][u] && a != con2[i][u]){
v[i].second = false;
continue;
}
if(b != con1[i][vv] && b != con2[i][vv]){
v[i].second = false;
continue;
}
comp2[i][u] = vv;
if(a == con1[i][u] && b == con1[i][vv]){
con1[i][vv] = con2[i][u];
}
if(a == con2[i][u] && b == con1[i][vv]){
con1[i][vv] = con1[i][u];
}
if(a == con1[i][u] && b == con2[i][vv]){
con2[i][vv] = con2[i][u];
}
if(a == con2[i][u] && b == con2[i][vv]){
con2[i][vv] = con1[i][u];
}
}
ans = 0;
for(int i=0;i<(int)v.size();i++) ans+=v[i].second;
}
int CountCritical() {
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
24444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
443 ms |
44440 KB |
Output is correct |
| 2 |
Incorrect |
942 ms |
84972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
24444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
24444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
24444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
