#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
const int N = (int)1e6+9;
vector<int> v;
array<int,2> edges[N];
int n, s=-1, T=1, ok=1, totE;
struct Dsu{
bool bad[N];
vector<int> st, adj[N];
int node, numBad, cycSz;
int vis[N], p[N], sz[N], deg[N];
void dfs(int s, int p, vector<int> &st){
vis[s]=1; st.pb(s);
for(auto u : adj[s]){
if(u==p) continue;
if(!vis[u]) dfs(u,s,st);
else if(vis[u]==1){ cycSz++;
while(sz(st) and st.back()!=u)
cycSz++, st.pop_back();
return;
}
}
vis[s]=2; st.pop_back();
}
void init(int N){
st.clear(); node = -1; numBad=cycSz=0;
for(int i = 0; i < N; i++){
adj[i].clear(); p[i]=i,sz[i]=1;
bad[i]=vis[i]=deg[i]=0;
}
}
int findSet(int i){ return i==p[i]?i:p[i]=findSet(p[i]); }
void unionSet(int i, int j){
if(i==node or j==node) return;
deg[i]++, deg[j]++, adj[i].pb(j), adj[j].pb(i);
int x = findSet(i), y = findSet(j);
if(x==y){
if(!cycSz) st.clear(),dfs(i,-1,st);
if(!bad[x]) numBad++, bad[x]=1;
return;
}
numBad-=bad[x]+bad[y];
if(sz[x]<sz[y]) swap(x,y);
p[y] = x; sz[x]+=sz[y];
if(bad[x]||bad[y]||deg[i]>2||deg[j]>2)
bad[x]=bad[y]=1, numBad++;
}
} dsu[5];
void Init(int n_) { n = n_; for(int i=0;i<5;i++) dsu[i].init(n); }
void Link(int a, int b) {
for(int i=0;i<T;i++) dsu[i].unionSet(a,b);
if(dsu[0].deg[a]==4 and sz(v)<=1) v.pb(a);
if(dsu[0].deg[b]==4 and sz(v)<=1) v.pb(b);
if(dsu[0].deg[a]==3 and s==-1) s=a;
if(dsu[0].deg[b]==3 and s==-1) s=b;
edges[totE++]={a,b};
}
int CountCritical(){
if(sz(v)>=2 or dsu[0].numBad>=2) return 0;
if(!dsu[0].numBad) return n;
if(sz(v)==1){
if(ok){
dsu[T++].node = v[0]; ok=0;
for(int i = 0; i < totE; i++)
dsu[1].unionSet(edges[i][0],edges[i][1]);
}
return !dsu[1].numBad;
}
if(s==-1) return dsu[0].cycSz;
if(ok){
dsu[T++].node=s; ok = 0;
for(auto u : dsu[0].adj[s]) dsu[T++].node=u;
for(int j = 1; j < T; j++)
for(int i = 0; i < totE; i++)
dsu[j].unionSet(edges[i][0],edges[i][1]);
}
int ans=0;for(int i=1;i<T;i++)ans+=!dsu[i].numBad; return ans;
}
Compilation message
rings.cpp: In member function 'void Dsu::init(int)':
rings.cpp:32:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
32 | bad[i]=vis[i]=deg[i]=0;
| ~~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
117788 KB |
Output is correct |
2 |
Correct |
58 ms |
118616 KB |
Output is correct |
3 |
Correct |
59 ms |
118632 KB |
Output is correct |
4 |
Incorrect |
60 ms |
117952 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
377 ms |
181952 KB |
Output is correct |
2 |
Correct |
1247 ms |
241080 KB |
Output is correct |
3 |
Runtime error |
1034 ms |
262144 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
117788 KB |
Output is correct |
2 |
Correct |
58 ms |
118616 KB |
Output is correct |
3 |
Correct |
59 ms |
118632 KB |
Output is correct |
4 |
Incorrect |
60 ms |
117952 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
117788 KB |
Output is correct |
2 |
Correct |
58 ms |
118616 KB |
Output is correct |
3 |
Correct |
59 ms |
118632 KB |
Output is correct |
4 |
Incorrect |
60 ms |
117952 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
117788 KB |
Output is correct |
2 |
Correct |
58 ms |
118616 KB |
Output is correct |
3 |
Correct |
59 ms |
118632 KB |
Output is correct |
4 |
Incorrect |
60 ms |
117952 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |