Submission #1326365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326365		SSKMF	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	96 ms	22132 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++) {
		for (int nod_2 = 0 ; nod_2 < numar_noduri ; nod_2++) {
			if (modalitati[nod_1][nod_2] == 3)
				{ 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; }
		}

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

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

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

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

		if (luat.size() == 2)
			{ 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;
	}
	
	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: 4 / 4