#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
//#define endl '\n'
int n;
int co=0;
int st=0;
int par[1000001][5];
set<int> adj[1000001];
vector<int> dd;
int vis[4];
int find(int no,int ind){
if(par[no][ind]==no){
return no;
}
par[no][ind]=find(par[no][ind],ind);
return par[no][ind];
}
int ans;
void Init(int N_) {
n = N_;
for(int j=0;j<5;j++){
for(int i=0;i<n;i++){
par[i][j]=i;
}
}
ans=n;
}
vector<pair<int,int>> ed;
void push(int aa,int bb,int ind){
if(dd[ind-1]==aa or dd[ind-1]==bb){
return ;
}
int x=find(aa,ind);
int y=find(bb,ind);
if(x==y){
vis[ind-1]=1;
// cout<<dd[ind-1]<<":<<"<<endl;
// cout<<aa<"::"<<bb<<ind<<endl;
}
else{
par[x][ind]=y;
}
}
vector<int> path;
vector<int> cot;
int vis2[1000001];
void dfs(int no,int aa,int bb){
vis2[no]=1;
// cout<<no<<",";
cot.pb(no);
for(auto j:adj[no]){
if(no==aa and j==bb){
continue;
}
if(vis2[j]){
path=cot;
}
else{
dfs(j,aa,bb);
}
}
cot.pop_back();
}
void find3(int aa,int bb){
dfs(aa,aa,bb);
}
void Link(int aa, int bb){
ed.pb({aa,bb});
if(st){
for(int i=0;i<dd.size();i++){
push(aa,bb,i+1);
}
}
int prev=st;
/*if(st){
vector<int> dd;
int k=0;
for(auto j:cur){
k+=1;
if(j==aa or j==bb){
continue;
}
int x=find(aa,k);
int y=find(bb,k);
if(x==y){
dd.pb(j);
}
else{
par[x][j]=y;
}
}
for(auto j:dd){
cur.erase(j);
}
}*/
adj[aa].insert(bb);
// cout<<adj[aa].size()<<"...."<<endl;
if(adj[aa].size()==3){
if(st==0){
st=1;
dd.pb(aa);
for(auto j:adj[aa]){
dd.pb(j);
// cout<<j<<"<";
}
// cout<<endl;
}
else{
for(int i=0;i<dd.size();i++){
int stt=0;
if(dd[i]==aa){
stt=1;
}
for(auto j:adj[aa]){
if(dd[i]==j){
stt=1;
}
}
if(stt==0){
vis[i]=1;
// cout<<i<<"<........<"<<endl;
}
}
}
}
else if(adj[aa].size()==4){
if(st==0){
vis[1]=1;
vis[2]=1;
vis[3]=1;
dd.pb(aa);
st=1;
}
else{
for(int i=0;i<dd.size();i++){
if(dd[i]!=aa){
vis[i]=1;
}
}
}
}
swap(aa,bb);
adj[aa].insert(bb);
if(adj[aa].size()==3){
if(st==0){
st=1;
dd.pb(aa);
for(auto j:adj[aa]){
dd.pb(j);
}
}
else{
for(int i=0;i<dd.size();i++){
int stt=0;
if(dd[i]==aa){
stt=1;
}
for(auto j:adj[aa]){
if(dd[i]==j){
stt=1;
}
}
if(stt==0){
vis[i]=1;
// cout<<i<<"<........<"<<endl;
}
}
}
}
else if(adj[aa].size()==4){
if(st==0){
vis[1]=1;
vis[2]=1;
vis[3]=1;
dd.pb(aa);
st=1;
}
else{
for(int i=0;i<dd.size();i++){
if(dd[i]!=aa){
vis[i]=1;
}
}
}
}
// cout<<111<<"<"<<prev<<"<"<<st<<endl;
if(prev==0 and st==1){
// cout<<11<<endl;
for(int i=0;i<dd.size();i++){
// cout<<dd[i]<<"/";
for(auto j:ed){
push(j.a,j.b,i+1);
}
}
// cout<<endl;
}
if(st==0){
int x=find(aa,0);
int y=find(bb,0);
if(x!=y){
par[x][0]=y;
}
else{
co+=1;
if(co==1){
find3(aa,bb);
ans=path.size();
// cout<<endl;
}
else{
ans=0;
}
}
}
}
int CountCritical(){
if(ans==0){
return 0;
}
if(st){
int ans2=0;
for(int i=0;i<4;i++){
ans2+=1-vis[i];
}
return ans2;
}
else{
return ans;
}
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/
/*
g++ -DEVAL -Wall -static -O2 -o aa grader.cpp rings.cpp
*/
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:144:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:162:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:189:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:199:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
36 ms |
48000 KB |
Output is correct |
| 3 |
Correct |
38 ms |
47992 KB |
Output is correct |
| 4 |
Incorrect |
36 ms |
47480 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
670 ms |
117212 KB |
Output is correct |
| 2 |
Correct |
1371 ms |
154932 KB |
Output is correct |
| 3 |
Correct |
1966 ms |
175748 KB |
Output is correct |
| 4 |
Incorrect |
1581 ms |
183544 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
36 ms |
48000 KB |
Output is correct |
| 3 |
Correct |
38 ms |
47992 KB |
Output is correct |
| 4 |
Incorrect |
36 ms |
47480 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
36 ms |
48000 KB |
Output is correct |
| 3 |
Correct |
38 ms |
47992 KB |
Output is correct |
| 4 |
Incorrect |
36 ms |
47480 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
36 ms |
48000 KB |
Output is correct |
| 3 |
Correct |
38 ms |
47992 KB |
Output is correct |
| 4 |
Incorrect |
36 ms |
47480 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
