Submission #241687

#	Time	Username	Problem	Language	Result	Execution time	Memory
241687		kshitij_sodani	Parachute rings (IOI12_rings)	C++17	0 / 100	1966 ms	183544 KiB

rings

#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 (stderr)

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++){
               ~^~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31