Rezultati

Up. imeNalogaJezikRezultatČas oddaje
zgancejem-2019 Barvanje drevesa C++ 100/100OK 24. apr '19 @ 17:12

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 3,039 MiB 0,000 s OK
#2 [več] 10/10 3,039 MiB 0,004 s OK
#3 [več] 10/10 3,039 MiB 0,004 s OK
#4 [več] 10/10 3,035 MiB 0,004 s OK
#5 [več] 10/10 3,039 MiB 0,000 s OK
#6 [več] 10/10 3,039 MiB 0,000 s OK
#7 [več] 10/10 3,039 MiB 0,010 s OK
#8 [več] 10/10 3,051 MiB 0,004 s OK
#9 [več] 10/10 3,063 MiB 0,010 s OK
#10 [več] 10/10 3,188 MiB 0,010 s OK

Ocenjevani program (f.cpp):
#include <iostream>

using namespace std;

struct A {
	A *dad, *levi, *desni;
	int colour;
	A() :dad(NULL), levi(NULL), desni(NULL), colour(1) { }
	A *findRoot() {
		if (dad == NULL) {
			return this;
		}
		return dad->findRoot();
	}
	void Colour(int *globina, int glob = 0) {
		if (dad != NULL) {
			if (dad->colour == colour) {
				colour++;
				Colour(globina, glob);
				return;
			}
		}
		
		
		if (globina[glob] == colour) {
			colour++;
			Colour(globina, glob);
			return;
		}

		if (levi != NULL) {
			levi->Colour(globina, glob + 1);
		}
		if (desni != NULL) {
			desni->Colour(globina, glob + 1);
		}
		globina[glob] = colour;
	}
};

int main()
{
	A *arr = new A[1001];
	int *globina = new int[1001];
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		globina[i - 1] = 0;
		int l, r;
		cin >> l >> r;
		if(l)
			arr[i].levi = &arr[l], arr[l].dad = &arr[i];
		if (r)
			arr[i].desni = &arr[r], arr[r].dad = &arr[i];
	}
	/*for (int i = 1; i <= N; i++)
	{
		cout << i << ". " << &arr[i] << " " << arr[i].levi << " " << arr[i].desni << " "  <<  arr[i].dad << "\n";
	}*/

	A *root = arr[1].findRoot();
	
	root->Colour(globina);


	for (int i = 1; i <= N; i++)
	{
		cout << arr[i].colour << " ";
	}
	//cin >> N; // popraviiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
	//
    return 0;
}