Submission #117687

#	Time	Username	Problem	Language	Result	Execution time	Memory
117687		rajarshi_basu	Parachute rings (IOI12_rings)	C++14	37 / 100	3642 ms	141312 KiB

rings

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000*100*10+10;
const int MAXVAL = 1e9+10;

int CountCritical();

// stage 1 means that all have degree atmost 2
// stage 2 means that there is degree atmost 3,
// stage 3 means that there is a node of degree 4 or higher.
int stage = 1;
int deg[MAXN];

vi g[MAXN];
vector<ii> edges;

int n;

struct DSU{
	int parent[MAXN];
	int compSize[MAXN];
	int ID = 0;
	void init(int n, bool b=0){
		//parent = new int[n];
		//if(b)compSize = new int[n];
		
		FOR(i,n)parent[i] = i;
		FOR(i,n)compSize[i] = 1;
	}
	inline int find(int a){
		if(parent[a] != a)parent[a] = find(parent[a]);
		return parent[a];
	}
	inline void merge(int a,int b){
		int pa = find(a);
		int pb = find(b);
		parent[pa] = pb;
		compSize[pb] += compSize[pa];
	}
	inline bool isSame(int a,int b){
		return find(a) == find(b);
	}
	inline int sizeOf(int a){
		return compSize[find(a)];
	}
};	

DSU dsu1;
set<int> impNodes;
DSU dsu[5];
int degindi[5][MAXN];
bool sedd[5];

vi impNd;
set<int> componentWithHighDeg;
int componentWithCycle;
bool doomed;

void Init(int N){
	doomed = false;
	n = N;//gdsu = new DSU(n);
	dsu1.init(n,1);
	componentWithCycle = -1;
}

int cntDeg;
void initStage2(int a,int b){
	impNd.clear();
	impNodes.clear();
	/*
	FOR(i,10){
		dsu[i].init(n);
		FOR(j,MAXN)degindi[i][j] = 0;
		sedd[i] = 0;
	}*/

	stage = 2;
	int ctr = 0;
	
	cntDeg = ctr;
	if(ctr <= 2){
		// all the neighbours are also important too
		FOR(i,n){
			if(deg[i] > 2){
				impNodes.insert(i);
				for(auto e:g[i])impNodes.insert(e);

				break;
			}
		}
	}else{
		FOR(i,n){
			if(deg[i] > 2){
				impNodes.insert(i);
			}
		}
	}
	for(auto e : impNodes){
		impNd.pb(e);
	}
	int xx = 0;
	for(auto x : impNd){
		dsu[xx].init(n);
		//cout << "xx : " <<  xx << endl;
		sedd[xx] = 0;
		FOR(j,MAXN)degindi[xx][j] = 0;
		for(auto edge : edges){
			if(edge.ff == x or edge.ss == x)continue;
			degindi[xx][edge.ff]++;
			degindi[xx][edge.ss]++;
			// see if the graph has any 3deg nodes left
			if(max(degindi[xx][edge.ff],degindi[xx][edge.ss]) > 2){
				sedd[xx] = 1;
			}else{
				// check if graph has any cycles remaining
				if(dsu[xx].isSame(edge.ff,edge.ss)){
					sedd[xx] = 1;
				}else{
					dsu[xx].merge(edge.ff,edge.ss);
				}
			}
		}
		xx++;
	}

}

void initStage3(){
	set<int> deg4;
	dsu[4].init(n);
	FOR(i,n){
		if(deg[i] >= 4){
			deg4.insert(i);
		}
	}
	if(deg4.size() > 1){
		doomed = 1;
		return;
	}else{
		impNd.clear();
		for(auto e : deg4){
			impNd.pb(e);
		}
		int mynode = impNd[0];
		
		//cout << mynode << endl;
 		for(auto e : edges){
			if(e.ff == mynode or e.ss == mynode)continue;
			degindi[4][e.ff]++;
			degindi[4][e.ss]++;
			if(dsu[4].isSame(e.ff,e.ss)){
				//cout << e.ff << " " << e.ss << endl;
				//cout << dsu[4].find(e.ff) << " " << dsu[4].find(e.ss) << endl;
				//cout << "MEHH" << endl;
				doomed = 1;
			}else{
				dsu[4].merge(e.ff,e.ss);
			}
		}
	}
}
bool reset = 0;

void Link(int a,int b){
	g[a].pb(b);
	g[b].pb(a);
	edges.pb({a,b});
	deg[a]++;
	deg[b]++;
	if(doomed)return;
	if(stage == 1){

		if(deg[a] > 2 or deg[b] > 2){
	//		cout << "INITING STAGE 2" << endl;
			initStage2(a,b);
		}else{
	//		cout << "PROCESSING IN STAGE 1" << endl;
			// we still have atmost degree 2
			if(dsu1.isSame(a,b)){
				// this means we are creating a cycle in this component.
				if(componentWithCycle == -1){
					// this means this is the first component with the cycle
					componentWithCycle = dsu1.find(a);
				}else{
					doomed = true;
				}
			}else{
				dsu1.merge(a,b);
			}
		}
	}else if(stage == 2){
		if(deg[a] > 3 or deg[b] > 3){
	//		cout << "INITING STAGE 3" << endl;
			initStage3();
		} else {

			int xx = 0;
			
	//		cout << "PROCESSING in STAGE 2" << endl;
			for(auto x : impNd){
				if(a == x or b == x){
					xx++;
					continue;
				}
	//			cout << "xx : " <<  xx << endl;
				degindi[xx][a]++;
				degindi[xx][b]++;
				if(max(degindi[xx][a], degindi[xx][b]) > 2){
					sedd[xx] = 1;
				}else{
					if(dsu[xx].isSame(a,b)){
						sedd[xx] = 1;
					}else{
						dsu[xx].merge(a,b);
					}
				}
				xx++;
			}
		}
	}else if(stage == 3){
	//	cout << "PROCESSING STAGE 3" << endl;
		int mynode = impNd[0];
		if(deg[a] > 3 and mynode != a){
			doomed = 1;
		} else if(deg[b] > 3 and mynode != b){
			doomed = 1;
		} else {
			if(a == mynode or b == mynode)return;
			degindi[4][a]++;
			degindi[4][b]++;
			if(degindi[4][a] > 2 or degindi[4][b] > 2){
				doomed = 1;
			} else {
				if(dsu[4].isSame(a,b)){
					doomed = 1;
				}else{
					dsu[4].merge(a,b);
				}
			}
		}

	}

	//cout << CountCritical() << endl;
}
/*
inline bool isCritical(int x){
	DSU dsu(n);
	int deg[n];
	FOR(i,n)deg[i] = 0;

	for(auto e : edges){
		if(e.ff == x or e.ss == x)continue;
		deg[e.ff]++;
		deg[e.ss]++;
		if(dsu.find(e.ff) == dsu.find(e.ss)){

			return 0;
		}
		dsu.merge(e.ff,e.ss);
	}
	FOR(i,n)if(deg[i] > 2)return 0;
	return 1;
}*/

int CountCritical(){
	if(doomed)return 0;
	if(stage == 1 and componentWithCycle == -1){
		return n;
	}
	if(stage == 1 and componentWithCycle != -1){
		return dsu1.sizeOf(componentWithCycle);
	}
	if(stage == 2){
		int ctr = 0;
		FOR(i,impNd.size()){
			ctr += !sedd[i];
		}
		return ctr;
	}
	while(1);
	return 1;
}

int m1ain(){
	Init(10);
	//cout << CountCritical() << endl;
	Link(0,1);
	Link(1,2);
	Link(2,0);
	Link(2,3);
	Link(2,4);
	/*
	Link(4,5);
	Link(5,6);
	Link(4,6);
	*/
	return 0;
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
rings.cpp:308:7:
   FOR(i,impNd.size()){
       ~~~~~~~~~~~~~~           
rings.cpp:308:3: note: in expansion of macro 'FOR'
   FOR(i,impNd.size()){
   ^~~

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