Rezultati

Up. imeNalogaJezikRezultatČas oddaje
final-solution-2019 Barvanje drevesa C 100/100OK 24. apr '19 @ 18:44

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 1,457 MiB 0,000 s OK
#2 [več] 10/10 1,461 MiB 0,000 s OK
#3 [več] 10/10 1,457 MiB 0,000 s OK
#4 [več] 10/10 1,461 MiB 0,000 s OK
#5 [več] 10/10 1,461 MiB 0,000 s OK
#6 [več] 10/10 1,508 MiB 0,000 s OK
#7 [več] 10/10 1,480 MiB 0,005 s OK
#8 [več] 10/10 1,516 MiB 0,011 s OK
#9 [več] 10/10 1,496 MiB 0,017 s OK
#10 [več] 10/10 1,512 MiB 0,005 s OK

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

struct node {
    int p, ca, cb, sa, sb;
    int leg;
    int color;
};

static struct node T[1002];

static int tree_leftmost(int i, int h) {
    if (h < 0 || !i) return 0;
    if (!h) return i;
    int j = tree_leftmost(T[i].ca, h - 1);
    if (j) return j;
    return tree_leftmost(T[i].cb, h - 1);
}

static int tree_rightmost(int i, int h) {
    if (h < 0 || !i) return 0;
    if (!h) return i;
    int j = tree_rightmost(T[i].cb, h - 1);
    if (j) return j;
    return tree_rightmost(T[i].ca, h - 1);
}

static int sibling_left(int i) {
    int h = 0;
    while (i) {
        if (T[i].leg) {
            int j = tree_rightmost(T[T[i].p].ca, h);
            if (j) return j;
        }
        i = T[i].p;
        h++;
    }
    return 0;
}

static int sibling_right(int i) {
    int h = 0;
    while (i) {
        if (!T[i].leg) {
            int j = tree_leftmost(T[T[i].p].cb, h);
            if (j) return j;
        }
        i = T[i].p;
        h++;
    }
    return 0;
}

static void flood(int r) {
    if (!r) return;
    if (T[r].color) return;
    int u = 0;
    u |= (1 << T[T[r].p].color);
    u |= (1 << T[T[r].ca].color);
    u |= (1 << T[T[r].cb].color);
    u |= (1 << T[T[r].sa].color);
    u |= (1 << T[T[r].sb].color);
    if (!(u & 2)) T[r].color = 1;
    else if (!(u & 4)) T[r].color = 2;
    else if (!(u & 8)) T[r].color = 3;
    else T[r].color = 4;
    flood(T[r].ca);
    flood(T[r].cb);
}

int main() {
    int i = 0, n = 0, r = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        T[i].ca = a;
        T[i].cb = b;
        if (a) {
            T[a].p = i;
            T[a].leg = 0;
        }
        if (b) {
            T[b].p = i;
            T[b].leg = 1;
        }
    }
    for (i = 1; i <= n; i++) {
        T[i].sa = sibling_left(i);
        T[i].sb = sibling_right(i);
        if (!T[i].p) r = i;
    }
    flood(r);
    for (i = 1; i <= n; i++) {
        if (i != 1) printf(" ");
        printf("%d", T[i].color);
    }
    printf("\n");
    return 0;
}