Submission #117613

#	Time	Username	Problem	Language	Result	Execution time	Memory
117613		rajarshi_basu	Parachute rings (IOI12_rings)	C++14	0 / 100	1084 ms	262144 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;

// 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;

set<int> deg3nds;

int n;
struct DSU{
	int* parent;
	int* compSize;
	void init(int n){
		parent = new int[n];
		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[20];
int degindi[20][MAXN];
bool sedd[20];

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

void Init(int N){
	doomed = false;
	n = N;//gdsu = new DSU(n);
	dsu1.init(n);
	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;
	FOR(i,n){
		if(deg[i] > 2){
			ctr++;
			deg3nds.insert(i);
		}
	}
	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);
			}
		}
	}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);
		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;
	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];
		FOR(i,n){
			degindi[19][i] = deg[i];
		}
		for(auto e : g[mynode]){
			degindi[19][e]--;
		}
		for(auto e : edges){
			if(e.ff == mynode or e.ss == mynode)continue;
			if(dsu[19].isSame(e.ff,e.ss)){
				doomed = 1;
			}else{
				dsu[19].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(deg[a] > 2){
		deg3nds.insert(deg[a]);
	}
	if(deg[b] > 2){
		deg3nds.insert(deg[b]);
	}
	if(doomed)return;
	if(stage == 1){
		if(deg[a] > 2 or deg[b] > 2){
			initStage2(a,b);
		}else{
			// 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){
			initStage3();
		} else {
			int xx = 0;
			if(deg3nds.size() > 2 and !reset){
				initStage2(a,b);
				reset = 1;
				return;
			}
			for(auto x : impNd){
				if(a == x or b == x){
					xx++;
					continue;
				}
				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){
		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[19][a]++;
			degindi[19][b]++;
			if(degindi[19][a] > 2 or degindi[19][b] > 2){
				doomed = 1;
			} else {
				if(dsu[19].isSame(a,b)){
					doomed = 1;
				}else{
					dsu[19].merge(a,b);
				}
			}
		}

	}
}
/*
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;
	}
	
	return 1;
}
/*
int main(){
	Init(7);
	cout << CountCritical() << endl;
	Link(1,2);
	cout << CountCritical() << endl;
	Link(0,5);
	cout << CountCritical() << endl;
	Link(0,2);
	cout << CountCritical() << endl;
	Link(3,2);
	cout << CountCritical() << endl;
	Link(3,5);
	cout << CountCritical() << endl;
	Link(3,4);
	cout << CountCritical() << endl;
	

	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:301:7:
   FOR(i,impNd.size()){
       ~~~~~~~~~~~~~~           
rings.cpp:301:3: note: in expansion of macro 'FOR'
   FOR(i,impNd.size()){
   ^~~

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