#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define EL cout<<'\n'
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
out<<'('<<P.F<<','<<P.S<<')';
return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
REP(i,SZ(V)) out<<V[i]<<((i!=SZ(V)-1)?" ":"");
return out;
}
#define version 20190726
//}}}
const ll maxn=1000005;
const ll maxlg=20;
const ll INF64=1e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;
ll mypow(ll a,ll b){
ll res=1LL;
while(b){
if(b&1) res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
int n;
int dsu[maxn],sz[maxn];
vector<int> ring;
int notst=0;
int deg[maxn];
vector<int> v;
bool vis[maxn];
vector<int> edge[maxn];
int find(int u){
if(dsu[u]==u) return u;
return dsu[u]=find(dsu[u]);
}
void mrg(int u,int v){
u=find(u);
v=find(v);
if(u==v) return;
if(sz[u]<sz[v]) swap(u,v);
dsu[v]=u;
sz[u]+=sz[v];
}
void Init(int N_) {
n = N_;
REP(i,n) dsu[i]=i,sz[i]=1;
REP(i,n) ring.pb(i);
v=ring;
}
vector<int> path;
vector<int> _r;
void dfs(int u,int par){
// cout<<u<<' '<<par<<'\n';
vis[u]=1;
path.pb(u);
for(int v:edge[u]) if(v!=par){
if(vis[v]){
if(SZ(_r)!=0) continue;
for(int i=SZ(path)-1;i>=0;i--){
_r.pb(path[i]);
if(path[i]==v) break;
}
}
else{
dfs(v,u);
}
}
path.pop_back();
}
void Link(int A, int B) {
deg[A]++;
deg[B]++;
edge[A].pb(B);
edge[B].pb(A);
if(find(A)==find(B)){
notst++;
if(notst==1){
REP(i,n) if(!vis[i]) dfs(i,-1);
ring=_r;
sort(ALL(ring));
}
}
else{
mrg(A,B);
}
// cout<<"???: "<<A<<' '<<B<<'\n';
if(deg[A]>3||deg[B]>3){
notst=880301;
}
if(deg[A]==3){
vector<int> nw;
for(int i:v){
bool f=(i==A);
for(int j:edge[A]) if(j==i) f=1;
if(f) nw.pb(i);
}
sort(ALL(nw));
v=nw;
}
if(deg[B]==3){
vector<int> nw;
for(int i:v){
bool f=(i==B);
for(int j:edge[B]) if(j==i) f=1;
if(f) nw.pb(i);
}
sort(ALL(nw));
v=nw;
}
}
int CountCritical() {
// cout<<"Info: "<<notst<<' '<<SZ(v)<<' '<<SZ(ring)<<'\n';
if(notst>=2){
return 0;
}
if(SZ(v)==n) return SZ(ring);
int ans=0;
for(int i:v){
int l=0,r=SZ(ring);
while(l<r-1){
int mid=(l+r)/2;
if(ring[mid]<=i) l=mid;
else r=mid;
}
ans+=ring[l]==i;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23848 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
24184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
489 ms |
50816 KB |
Output is correct |
| 2 |
Incorrect |
995 ms |
65120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23848 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
24184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23848 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
24184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
23848 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
24184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
