Submission #1326269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326269		SSKMF	슈퍼트리 잇기 (IOI20_supertrees)	C++20	11 / 100	92 ms	22084 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 nod_1 = 0 ; nod_1 < numar_noduri ; nod_1++)
	{
		if (modalitati[nod_1][nod_1] != 1)
			{ return 0; }

		for (int nod_2 = nod_1 + 1 ; nod_2 < numar_noduri ; nod_2++) {
			if (modalitati[nod_1][nod_2] != modalitati[nod_2][nod_1])
				{ return 0; }
		}
	}

	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);
	}

	for (auto& nod_1 : ramas) {
		for (auto& nod_2 : ramas) {
			for (int indice = 0 ; indice < numar_noduri ; indice++) {
				if (modalitati[nod_1][indice] && !modalitati[nod_2][indice])
					{ return 0; }
			}
		}
	}

	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]] > 1)
				{ 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_1 : luat) {
			for (auto& nod_2 : luat) {
				if (nod_1 != nod_2 && modalitati[nod_1][nod_2] != dorit)
					{ 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: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4