oj.uz

Submission #117687

# Submission time Handle Problem Language Result Execution time Memory
117687 2019-06-17T06:19:47 Z rajarshi_basu Parachute rings (IOI12_rings) C++14
37 / 100
 3642 ms 141312 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 37 ms 40064 KB Output is correct
3 Correct 38 ms 40056 KB Output is correct
4 Correct 23 ms 23908 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 26 ms 24156 KB Output is correct
7 Correct 36 ms 39784 KB Output is correct
8 Correct 24 ms 24164 KB Output is correct
9 Correct 37 ms 40064 KB Output is correct
10 Correct 37 ms 40160 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 50380 KB Output is correct
2 Correct 2105 ms 114800 KB Output is correct
3 Correct 1200 ms 141312 KB Output is correct
4 Correct 1638 ms 86740 KB Output is correct
5 Correct 1607 ms 86644 KB Output is correct
6 Correct 1775 ms 85596 KB Output is correct
7 Correct 1192 ms 140368 KB Output is correct
8 Correct 3599 ms 128608 KB Output is correct
9 Correct 3642 ms 133648 KB Output is correct
10 Correct 978 ms 85332 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 37 ms 40064 KB Output is correct
3 Correct 38 ms 40056 KB Output is correct
4 Correct 23 ms 23908 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 26 ms 24156 KB Output is correct
7 Correct 36 ms 39784 KB Output is correct
8 Correct 24 ms 24164 KB Output is correct
9 Correct 37 ms 40064 KB Output is correct
10 Correct 37 ms 40160 KB Output is correct
11 Correct 37 ms 40196 KB Output is correct
12 Correct 40 ms 40696 KB Output is correct
13 Incorrect 40 ms 40700 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 37 ms 40064 KB Output is correct
3 Correct 38 ms 40056 KB Output is correct
4 Correct 23 ms 23908 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 26 ms 24156 KB Output is correct
7 Correct 36 ms 39784 KB Output is correct
8 Correct 24 ms 24164 KB Output is correct
9 Correct 37 ms 40064 KB Output is correct
10 Correct 37 ms 40160 KB Output is correct
11 Correct 37 ms 40196 KB Output is correct
12 Correct 40 ms 40696 KB Output is correct
13 Incorrect 40 ms 40700 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 37 ms 40064 KB Output is correct
3 Correct 38 ms 40056 KB Output is correct
4 Correct 23 ms 23908 KB Output is correct
5 Correct 24 ms 24056 KB Output is correct
6 Correct 26 ms 24156 KB Output is correct
7 Correct 36 ms 39784 KB Output is correct
8 Correct 24 ms 24164 KB Output is correct
9 Correct 37 ms 40064 KB Output is correct
10 Correct 37 ms 40160 KB Output is correct
11 Correct 554 ms 50380 KB Output is correct
12 Correct 2105 ms 114800 KB Output is correct
13 Correct 1200 ms 141312 KB Output is correct
14 Correct 1638 ms 86740 KB Output is correct
15 Correct 1607 ms 86644 KB Output is correct
16 Correct 1775 ms 85596 KB Output is correct
17 Correct 1192 ms 140368 KB Output is correct
18 Correct 3599 ms 128608 KB Output is correct
19 Correct 3642 ms 133648 KB Output is correct
20 Correct 978 ms 85332 KB Output is correct
21 Correct 37 ms 40196 KB Output is correct
22 Correct 40 ms 40696 KB Output is correct
23 Incorrect 40 ms 40700 KB Output isn't correct
24 Halted 0 ms 0 KB -