oj.uz

Submission #432849

# Submission time Handle Problem Language Result Execution time Memory
432849 2021-06-18T14:14:08 Z Mounir Parachute rings (IOI12_rings) C++14
0 / 100
 2752 ms 88648 KB 
#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];

		//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;
		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)
		return tCycle;
	return nNoeuds;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 43332 KB Output is correct
2 Correct 35 ms 43636 KB Output is correct
3 Correct 30 ms 43652 KB Output is correct
4 Incorrect 26 ms 43416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 63756 KB Output is correct
2 Correct 2065 ms 88648 KB Output is correct
3 Correct 2752 ms 82896 KB Output is correct
4 Incorrect 1316 ms 82420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 43332 KB Output is correct
2 Correct 35 ms 43636 KB Output is correct
3 Correct 30 ms 43652 KB Output is correct
4 Incorrect 26 ms 43416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 43332 KB Output is correct
2 Correct 35 ms 43636 KB Output is correct
3 Correct 30 ms 43652 KB Output is correct
4 Incorrect 26 ms 43416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 43332 KB Output is correct
2 Correct 35 ms 43636 KB Output is correct
3 Correct 30 ms 43652 KB Output is correct
4 Incorrect 26 ms 43416 KB Output isn't correct
5 Halted 0 ms 0 KB -