#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=1000010, LOG=20;
int n, m, k, u, v, x, y, t, a, b;
int tree=1, deg3, ans0, cycle;
int A[MAXN], B[MAXN], deg[MAXN];
vector<int> G[MAXN], V;
struct DSU{
int par[MAXN];
DSU(){
iota(par, par+MAXN, 0);
}
int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
int join(int x, int y){
x=get(x);
y=get(y);
par[x]=y;
return x!=y;
}
} dsu;
struct Solver{
int deg[MAXN], root, ok=1;
DSU dsu;
void add_edge(int u, int v){
if (u==root || v==root) return ;
ok&=dsu.join(u, v);
ok&=(2>=++deg[u]);
ok&=(2>=++deg[v]);
}
int Get(){ return ok;}
} solver[4];
void Init(int nn){
n=nn;
}
void Link(int u, int v){
if (ans0) return ;
if (deg3){
for (int i:{0, 1, 2, 3}) solver[i].add_edge(u, v);
return ;
}
A[m]=u;
B[m]=v;
m++;
deg[u]++;
deg[v]++;
if (deg[u]==3) swap(u, v);
if (deg[v]==3){
V={v};
for (int i=0; i<m; i++) if (A[i]==v || B[i]==v) V.pb(v^A[i]^B[i]);
for (int i:{0, 1, 2, 3}){
solver[i].root=V[i];
for (int j=0; j<m; j++) solver[i].add_edge(A[j], B[j]);
}
deg3=1;
return ;
}
if (dsu.join(u, v)) return ;
if (tree) tree=0;
else ans0=1;
}
int CountCritical(){
if (ans0) return 0;
if (deg3){
int res=0;
for (int i:{0, 1, 2, 3}) res+=solver[i].Get();
return res;
}
if (tree) return n;
int res=0;
for (int i=0; i<n; i++) if (dsu.get(i)==dsu.get(cycle)) res++;
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
43372 KB |
Output is correct |
| 2 |
Correct |
31 ms |
43500 KB |
Output is correct |
| 3 |
Correct |
31 ms |
43628 KB |
Output is correct |
| 4 |
Incorrect |
30 ms |
43500 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
213 ms |
49600 KB |
Output is correct |
| 2 |
Correct |
794 ms |
61292 KB |
Output is correct |
| 3 |
Correct |
1587 ms |
63124 KB |
Output is correct |
| 4 |
Incorrect |
471 ms |
55148 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
43372 KB |
Output is correct |
| 2 |
Correct |
31 ms |
43500 KB |
Output is correct |
| 3 |
Correct |
31 ms |
43628 KB |
Output is correct |
| 4 |
Incorrect |
30 ms |
43500 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
43372 KB |
Output is correct |
| 2 |
Correct |
31 ms |
43500 KB |
Output is correct |
| 3 |
Correct |
31 ms |
43628 KB |
Output is correct |
| 4 |
Incorrect |
30 ms |
43500 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
43372 KB |
Output is correct |
| 2 |
Correct |
31 ms |
43500 KB |
Output is correct |
| 3 |
Correct |
31 ms |
43628 KB |
Output is correct |
| 4 |
Incorrect |
30 ms |
43500 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
