Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 1,469 MiB 0,000 s OK
#2 [več] 10/10 1,469 MiB 0,000 s OK
#3 [več] 10/10 1,492 MiB 0,000 s OK
#4 [več] 10/10 1,465 MiB 0,000 s OK
#5 [več] 10/10 1,496 MiB 0,005 s OK
#6 [več] 10/10 1,496 MiB 0,005 s OK
#7 [več] 10/10 1,523 MiB 0,005 s OK
#8 [več] 10/10 1,523 MiB 0,005 s OK
#9 [več] 10/10 1,496 MiB 0,000 s OK
#10 [več] 10/10 1,520 MiB 0,000 s OK

Ocenjevani program (barvanjedrevesa.c):
#include<stdio.h>

struct Node{
	struct Node *parent, *children[2];
	char color;
	int depth;
};

struct Node tree[1000], *order[1000];
int spred, zad=1;

void dfs(struct Node * n){
	if(n->depth!=-1) return;
	if(n->parent==NULL){
		n->depth=0;
		order[0]=n;
		return;
	}
	dfs(n->parent);
	n->depth=n->parent->depth+1;
}

void set(struct Node * tren, struct Node * prev){
	char i, poss[3]={0, 0, 0};
	if(prev!=NULL && prev->depth==tren->depth){
		poss[prev->color]=1;
	}
	poss[tren->parent->color]=1;
	for(i=0;i<3;++i){
		if(poss[i]==0){
			tren->color=i;
			break;
		}
	}
}

int main(){
	int i, n, a, b;
	scanf("%d", &n);
	for(i=0;i<n;++i){
		scanf("%d %d", &a, &b);
		if(a==0) tree[i].children[0]=NULL;
		else{
			tree[i].children[0]=tree+a-1;
			tree[a-1].parent=tree+i;
		}
		if(b==0) tree[i].children[1]=NULL;
		else{
			tree[i].children[1]=tree+b-1;
			tree[b-1].parent=tree+i;
		}
		tree[i].depth=-1;
	}
	for(i=0;i<n;++i) dfs(tree+i);
	struct Node *tren, *prev;
	order[0]->color=0;
	if(order[0]->children[0]) order[zad++]=order[0]->children[0];
	if(order[0]->children[1]) order[zad++]=order[0]->children[1];
	++spred;
	prev=order[0];
	while(spred<zad){
		tren=order[spred];
		set(tren, prev);
		if(tren->children[0]) order[zad++]=tren->children[0];
		if(tren->children[1]) order[zad++]=tren->children[1];
		prev=tren;
		++spred;
	}
	for(i=0;i<n;++i){
		printf("%d ", tree[i].color+1);
	}
	putchar('\n');
	return 0;
}