Submission #432860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432860	2021-06-18T14:20:26 Z	Mounir	Parachute rings (IOI12_rings)	C++14	100 / 100	2883 ms	119104 KB

rings

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;

const int N = 1e6 + 5, N_VERSIONS = 5, GRAPHE = 4;
int nNoeuds;
int ens[N_VERSIONS][N], degre[N_VERSIONS][N];
int taille[N_VERSIONS][N];

int getEns(int iVersion, int noeud){
	if (ens[iVersion][noeud] != noeud)
		ens[iVersion][noeud] = getEns(iVersion, ens[iVersion][noeud]);
	return ens[iVersion][noeud];
}

vector<int> voisins[N];
int nSup4 = 0, nCycle;
vector<int> sups4;
bool bon[N_VERSIONS];
bool cycle;
int tCycle;
bool possible = true;

bool fusion(int iVersion, int noeud, int voisin){
	noeud = getEns(iVersion, noeud), voisin = getEns(iVersion, voisin);
	if (noeud == voisin){ //Cycle
		if (iVersion != GRAPHE || cycle){
			if (cycle && iVersion == GRAPHE)
				possible = false; 
			return false;		
		}
		cycle = true;
		tCycle = taille[iVersion][noeud];
		return true;
	}

	taille[iVersion][noeud] += taille[iVersion][voisin];
	ens[iVersion][voisin] = noeud;
	return true;
}

bool addArete(int iVersion, vector<int> noeuds){
	int noeud = noeuds[0], voisin = noeuds[1];
	noeud = getEns(iVersion, noeud), voisin = getEns(iVersion, voisin);
	if (noeud == voisin)
		return false;

	taille[iVersion][noeud] += taille[iVersion][voisin];
	ens[iVersion][voisin] = noeud;

	//cout << "add " << 

	for (int noeuda : noeuds){
		degre[iVersion][noeuda]++;
		if (degre[iVersion][noeuda] > 2)
			return false;
	}
	return true;
}

void construire(){
	for (int iVersion = 0; iVersion < 4; ++iVersion){
		int racine = sups4[iVersion];
		bon[iVersion] = true;

		//cout << "racine " << iVersion << " " << racine << endl;
		for (int noeud = 0; noeud < nNoeuds; ++noeud)
			for (int voisin : voisins[noeud]){
				if (noeud == racine || noeud < voisin || voisin == racine) continue;
				bool tmp;
				bon[iVersion] &= (tmp = addArete(iVersion, {noeud, voisin}));
				//cout << "bon " << noeud << " " << voisin << " " << tmp << endl;
				//bon[iVersion] &= (tmp = fusion(iVersion, noeud, voisin));
				//cout << "fusion " <<  noeud << " " << voisin << " " << tmp << endl;
			}
	}
}

void Init(int N_) {
	nNoeuds = N_;
	for (int iVersion = 0; iVersion < N_VERSIONS; ++iVersion){
		for (int noeud = 0; noeud < N; ++noeud){
			ens[iVersion][noeud] = noeud;
			taille[iVersion][noeud] = 1;
		}
		bon[iVersion] = true;
	}
}

void Link(int noeud, int voisin) {
	if (sz(sups4) > 0){
		for (int iVersion = 0; iVersion < 4; ++iVersion){
			int racine = sups4[iVersion];
			if (noeud == racine || voisin == racine) continue;
		//	cout << "LINK " << sups4[iVersion] << " " <<  noeud << " " << voisin << endl;

		//	bon[iVersion] &= fusion(iVersion, noeud, voisin);
			bon[iVersion] &= addArete(iVersion, {noeud, voisin});
		}
		return;
	}

	fusion(GRAPHE, noeud, voisin);


	degre[GRAPHE][noeud]++, degre[GRAPHE][voisin]++;
	voisins[noeud].pb(voisin);
	voisins[voisin].pb(noeud);
	nSup4 += (degre[GRAPHE][noeud] == 4) + (degre[GRAPHE][voisin] == 4);

	if (degre[GRAPHE][noeud] == 3 || degre[GRAPHE][voisin] == 3){
		if (degre[GRAPHE][noeud] != 3)
			swap(noeud, voisin);

		sups4.pb(noeud);
		for (int vSup : voisins[noeud])
			sups4.pb(vSup);

		/*cout << "sups4" << endl;
		for (int a : sups4)
			cout << a << " ";
		cout << endl;
*/
		construire();
	}
}

int CountCritical() {
	if (nSup4 >= 2 || (sz(sups4) == 0 && !possible))
		return 0;

	if (sz(sups4) > 0){
		//cout << "wsh wsh\n";
		int nb = 0;
		for (int iVersion = 0; iVersion < 4; ++iVersion){
		//	cout << "bon " << iVersion << " " << bon[iVersion] << endl;
			nb += bon[iVersion];
		}
		return nb;
	}

//	cout << "lala " <<cycle << " " << tCycle << endl;

	if (cycle){
	//	cout << "wsh wsh\n";
		return tCycle;
	}
	return nNoeuds;
}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	62804 KB	Output is correct
2	Correct	48 ms	63016 KB	Output is correct
3	Correct	44 ms	63084 KB	Output is correct
4	Correct	42 ms	62836 KB	Output is correct
5	Correct	46 ms	62968 KB	Output is correct
6	Correct	42 ms	63108 KB	Output is correct
7	Correct	44 ms	63044 KB	Output is correct
8	Correct	46 ms	63028 KB	Output is correct
9	Correct	52 ms	63168 KB	Output is correct
10	Correct	42 ms	63176 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	533 ms	81248 KB	Output is correct
2	Correct	1965 ms	92468 KB	Output is correct
3	Correct	2691 ms	82912 KB	Output is correct
4	Correct	1289 ms	97988 KB	Output is correct
5	Correct	1398 ms	104396 KB	Output is correct
6	Correct	1267 ms	103452 KB	Output is correct
7	Correct	2548 ms	89308 KB	Output is correct
8	Correct	2607 ms	113892 KB	Output is correct
9	Correct	2883 ms	119104 KB	Output is correct
10	Correct	924 ms	103300 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	62804 KB	Output is correct
2	Correct	48 ms	63016 KB	Output is correct
3	Correct	44 ms	63084 KB	Output is correct
4	Correct	42 ms	62836 KB	Output is correct
5	Correct	46 ms	62968 KB	Output is correct
6	Correct	42 ms	63108 KB	Output is correct
7	Correct	44 ms	63044 KB	Output is correct
8	Correct	46 ms	63028 KB	Output is correct
9	Correct	52 ms	63168 KB	Output is correct
10	Correct	42 ms	63176 KB	Output is correct
11	Correct	50 ms	63120 KB	Output is correct
12	Correct	48 ms	63532 KB	Output is correct
13	Correct	46 ms	63424 KB	Output is correct
14	Correct	44 ms	63148 KB	Output is correct
15	Correct	44 ms	63300 KB	Output is correct
16	Correct	51 ms	63344 KB	Output is correct
17	Correct	52 ms	63224 KB	Output is correct
18	Correct	47 ms	63424 KB	Output is correct
19	Correct	44 ms	63344 KB	Output is correct
20	Correct	47 ms	63488 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	62804 KB	Output is correct
2	Correct	48 ms	63016 KB	Output is correct
3	Correct	44 ms	63084 KB	Output is correct
4	Correct	42 ms	62836 KB	Output is correct
5	Correct	46 ms	62968 KB	Output is correct
6	Correct	42 ms	63108 KB	Output is correct
7	Correct	44 ms	63044 KB	Output is correct
8	Correct	46 ms	63028 KB	Output is correct
9	Correct	52 ms	63168 KB	Output is correct
10	Correct	42 ms	63176 KB	Output is correct
11	Correct	50 ms	63120 KB	Output is correct
12	Correct	48 ms	63532 KB	Output is correct
13	Correct	46 ms	63424 KB	Output is correct
14	Correct	44 ms	63148 KB	Output is correct
15	Correct	44 ms	63300 KB	Output is correct
16	Correct	51 ms	63344 KB	Output is correct
17	Correct	52 ms	63224 KB	Output is correct
18	Correct	47 ms	63424 KB	Output is correct
19	Correct	44 ms	63344 KB	Output is correct
20	Correct	47 ms	63488 KB	Output is correct
21	Correct	60 ms	64536 KB	Output is correct
22	Correct	75 ms	65412 KB	Output is correct
23	Correct	84 ms	66108 KB	Output is correct
24	Correct	112 ms	65380 KB	Output is correct
25	Correct	58 ms	64864 KB	Output is correct
26	Correct	97 ms	65784 KB	Output is correct
27	Correct	88 ms	67012 KB	Output is correct
28	Correct	130 ms	65820 KB	Output is correct
29	Correct	100 ms	65808 KB	Output is correct
30	Correct	127 ms	67640 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	62804 KB	Output is correct
2	Correct	48 ms	63016 KB	Output is correct
3	Correct	44 ms	63084 KB	Output is correct
4	Correct	42 ms	62836 KB	Output is correct
5	Correct	46 ms	62968 KB	Output is correct
6	Correct	42 ms	63108 KB	Output is correct
7	Correct	44 ms	63044 KB	Output is correct
8	Correct	46 ms	63028 KB	Output is correct
9	Correct	52 ms	63168 KB	Output is correct
10	Correct	42 ms	63176 KB	Output is correct
11	Correct	533 ms	81248 KB	Output is correct
12	Correct	1965 ms	92468 KB	Output is correct
13	Correct	2691 ms	82912 KB	Output is correct
14	Correct	1289 ms	97988 KB	Output is correct
15	Correct	1398 ms	104396 KB	Output is correct
16	Correct	1267 ms	103452 KB	Output is correct
17	Correct	2548 ms	89308 KB	Output is correct
18	Correct	2607 ms	113892 KB	Output is correct
19	Correct	2883 ms	119104 KB	Output is correct
20	Correct	924 ms	103300 KB	Output is correct
21	Correct	50 ms	63120 KB	Output is correct
22	Correct	48 ms	63532 KB	Output is correct
23	Correct	46 ms	63424 KB	Output is correct
24	Correct	44 ms	63148 KB	Output is correct
25	Correct	44 ms	63300 KB	Output is correct
26	Correct	51 ms	63344 KB	Output is correct
27	Correct	52 ms	63224 KB	Output is correct
28	Correct	47 ms	63424 KB	Output is correct
29	Correct	44 ms	63344 KB	Output is correct
30	Correct	47 ms	63488 KB	Output is correct
31	Correct	60 ms	64536 KB	Output is correct
32	Correct	75 ms	65412 KB	Output is correct
33	Correct	84 ms	66108 KB	Output is correct
34	Correct	112 ms	65380 KB	Output is correct
35	Correct	58 ms	64864 KB	Output is correct
36	Correct	97 ms	65784 KB	Output is correct
37	Correct	88 ms	67012 KB	Output is correct
38	Correct	130 ms	65820 KB	Output is correct
39	Correct	100 ms	65808 KB	Output is correct
40	Correct	127 ms	67640 KB	Output is correct
41	Correct	270 ms	76900 KB	Output is correct
42	Correct	1125 ms	98244 KB	Output is correct
43	Correct	394 ms	83048 KB	Output is correct
44	Correct	1651 ms	87684 KB	Output is correct
45	Correct	1769 ms	91016 KB	Output is correct
46	Correct	878 ms	99244 KB	Output is correct
47	Correct	1162 ms	99768 KB	Output is correct
48	Correct	930 ms	90964 KB	Output is correct
49	Correct	864 ms	98784 KB	Output is correct
50	Correct	908 ms	98472 KB	Output is correct
51	Correct	503 ms	83012 KB	Output is correct
52	Correct	1435 ms	84408 KB	Output is correct
53	Correct	908 ms	90052 KB	Output is correct
54	Correct	2145 ms	104484 KB	Output is correct
55	Correct	2070 ms	86984 KB	Output is correct

Submission #432860

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0