제출 #432860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432860		Mounir	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	2883 ms	119104 KiB

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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31