#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MAXN=1e6+100;
map <pii,int> mp;
vector <int> g[MAXN];
ll vis[MAXN];
vector <int> dig;
ll td=0;
ll p1=1;
ll ans=MAXN;
ll t4=0;
ll hazf[MAXN];
ll tool=0;
ll n;
ll ch[MAXN];
ll cnt=0;
vector <int> W;
ll par[MAXN];
ll dor[MAXN];
void del(ll v){
for (int i=0;i<n;i++){
vector <int> a;
for (auto u : g[i]) if (u!=v) a.pb(u);
g[i]=a;
}
g[v].clear();
hazf[v]=1;
}
void Init(ll N){
n=N;
ans=n;
for (int i=0;i<N;i++){
par[i]=i;
}
}
ll getpar(ll v){
if (par[v]==v) return v;
return par[v]=getpar(par[v]);
}
void rebuild(){
for (int i=0;i<MAXN;i++){
par[i]=i;
}
ans=1;
for (int i=0;i<n;i++) if (g[i].size()>2) p1=0;
for (int v=0;v<n;v++){
for (auto u : g[v]){
if (u>v){
ll u1=getpar(u);
ll v1=getpar(v);
if (u1==v1){
p1=0;
}
par[u1]=v1;
}
}
}
}
ll pa[MAXN];
ll hi[MAXN];
ll mark[MAXN];
ll dd(ll v,ll p){
mark[v]=1;
if (dor[v]==1) return v;
for (auto u : g[v]){
if (u==p || mark[v]) continue;
return dd(u,v);
}
return -1;
}
void dfs(ll v,ll p){
vis[v]=1;
hi[v]=hi[p]+1;
pa[v]=p;
for (auto u : g[v]){
if (u==p) continue;
if (vis[u]==1 && hi[u]>hi[v]){
ll z=u;
while(z!=v){
ch[z]++;
tool++;
dor[z]=1;
if (ch[z]==cnt) ans++,W.pb(z);
z=pa[z];
}
tool++;
dor[v]=1;
ch[v]++;
if (ch[v]==cnt) ans++,W.pb(v);
continue;
}
if (vis[u]) continue;
dfs(u,v);
}
}
void Link(int A, int B) {
if (p1==0 || ans==0) return ;
if (hazf[A] || hazf[B]) return ;
g[A].pb(B);
g[B].pb(A);
mp[{A,B}]=1;
mp[{B,A}]=1;
if (t4==1){
if (getpar(A)==getpar(B)) p1=0;
}
if (p1==0) return ;
// cout << "GOOOZ" << endl;
if (t4==1 && (g[A].size()>2 || g[B].size()>2)){
p1=0;
return ;
}
if (g[A].size()>3){
del(A);
rebuild();
return ;
}
if (g[B].size()>3){
del(A);
rebuild();
return ;
}
if (getpar(A)==getpar(B)){
// cout << "GOOZ" << endl;
if (td==0){
td++;
ans=0;
W.clear();
cnt++;
for (int i=0;i<n;i++){
if (vis[i]==0) dfs(i,i);
}
}
else if (td==1 && t4==0){
ll z=dd(A,B);
ll tz=dd(B,A);
if (mp[{z,tz}]){
cnt++;
W.clear();
ans=0;
ch[z]++;
if (ch[z]==cnt) ans++;
ch[tz]++;
if (ch[tz]==cnt) ans++;
// cout << ans << " erij " << endl;
}
// else p1=0;
}
}
else{
par[par[A]]=par[B];
}
if (g[B].size()==3){
t4=1;
// cout << "NR " << B << endl;
cnt++;
ans=0;
W.clear();
for (auto u : g[B]){
ch[u]++;
if (ch[u]==cnt) {
ans++;
W.pb(u);
// cout << u << " RAS " << endl;
}
}
ch[B]++;
// cout << ch[B] << " ascw" << endl;
if (ch[B]==cnt) W.pb(B),ans++;
}
if (g[A].size()==3){
t4=1;
// cout << " iurfrg " << endl;
cnt++;
ans=0;
W.clear();
for (auto u : g[A]){
ch[u]++;
if (ch[u]==cnt) {
ans++;
W.pb(u);
}
}
ch[A]++;
if (ch[A]==cnt) W.pb(A),ans++;
}
}
int CountCritical() {
/*
memset(vis,0,sizeof vis);
for (int i=0;i<n;i++){
if (vis[i]==0) dfs(i,i);
}
*/
if (t4) {
return p1;
}
if (p1==0) return 1/0;
return ans;
}
/*
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 ans\n", critical);
} else {
tmp = scanf("%d", &B);
assert(tmp == 1);
Link(A, B);
}
}
return 0;
}
*/
Compilation message
rings.cpp: In function 'int CountCritical()':
rings.cpp:217:24: warning: division by zero [-Wdiv-by-zero]
217 | if (p1==0) return 1/0;
| ~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
24428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1833 ms |
107628 KB |
Output is correct |
| 2 |
Incorrect |
1117 ms |
79724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
24428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
24428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23916 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
24428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
