제출 #1326363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326363		SSKMF	슈퍼트리 잇기 (IOI20_supertrees)	C++20	96 / 100	96 ms	22108 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int construct (vector< vector <int> > modalitati)
{
	const int numar_noduri = (int)modalitati.size();
	vector < vector <int> > adiacenta(numar_noduri , vector <int> (numar_noduri));
	vector <bool> vizitat(numar_noduri);
	vector <int> ramas;

	for (int inceput = 0 ; inceput < numar_noduri ; inceput++)
	{
		if (vizitat[inceput])
			{ continue; }

		vector <int> luat;
		for (int candidat = inceput ; candidat < numar_noduri ; candidat++)
		{
			if (modalitati[inceput][candidat] != 1)
				{ continue; }

			bool gasit = false;
			for (int indice = 0 ; indice < numar_noduri ; indice++) {
				if (gasit |= (modalitati[inceput][indice] != modalitati[candidat][indice]))
					{ break; }
			}
			
			if (!gasit)
				{ luat.push_back(candidat); vizitat[candidat] = true; }
			else
				{ return 0; }
		}

		bool gasit[2] = { };
		for (int nod = 0 ; nod < numar_noduri ; nod++) {
			if (modalitati[inceput][nod] != 1) {
				gasit[0] |= (modalitati[inceput][nod] == 2);
				gasit[1] |= (modalitati[inceput][nod] == 3);
			}
		}

		if (gasit[0] && gasit[1])
			{ return 0; }

		for (int indice = 0 ; indice + 1 < (int)luat.size() ; indice++)
			{ adiacenta[luat[indice]][luat[indice + 1]] = adiacenta[luat[indice + 1]][luat[indice]] = 1; }

		ramas.push_back(inceput);
	}

	vizitat.flip();
	for (int indice = 0 ; indice < (int)ramas.size() ; indice++)
	{
		int& nod = ramas[indice];
		if (vizitat[nod])
			{ continue; }

		int dorit = 0;
		vector <int> luat = {nod};
		for (int __indice = indice + 1 ; __indice < (int)ramas.size() ; __indice++) {
			if (modalitati[nod][ramas[__indice]])
				{ luat.push_back(ramas[__indice]); dorit = modalitati[nod][ramas[__indice]]; }
		}

		for (auto& __nod : luat)
			{ vizitat[__nod] = true; }

		if (luat.size() == 1)
			{ continue; }

		if (luat.size() == 2)
			{ return 0; }

		if (luat.size() == 3 && dorit == 3)
			{ return 0; }

		for (auto& __nod : luat) {
			for (int __indice = 0 ; __indice < numar_noduri ; __indice++) {
				if (modalitati[nod][__indice] != 1 && modalitati[__nod][__indice] != 1 && modalitati[nod][__indice] != modalitati[__nod][__indice])
					{ return 0; }
			}
		}

		for (int __indice = 0 ; __indice + 1 < (int)luat.size() ; __indice++) 
			{ adiacenta[luat[__indice]][luat[__indice + 1]] = adiacenta[luat[__indice + 1]][luat[__indice]] = 1; }

		adiacenta[luat[0]][luat.back()] = adiacenta[luat.back()][luat[0]] = 1;

		if (dorit == 3)
			{ adiacenta[luat[0]][luat[2]] = adiacenta[luat[2]][luat[0]] = 1; }
	}
	
	build(adiacenta);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4