Rezultati

Up. imeNalogaJezikRezultatČas oddaje
vlakec-tomaz-in-ekipa-raketa-2019 Barvanje drevesa Python 3 100/100OK 24. apr '19 @ 18:22

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 8,691 MiB 0,000 s OK
#2 [več] 10/10 8,465 MiB 0,000 s OK
#3 [več] 10/10 8,660 MiB 0,000 s OK
#4 [več] 10/10 8,672 MiB 0,000 s OK
#5 [več] 10/10 8,516 MiB 0,000 s OK
#6 [več] 10/10 8,813 MiB 0,000 s OK
#7 [več] 10/10 8,918 MiB 0,000 s OK
#8 [več] 10/10 8,973 MiB 0,000 s OK
#9 [več] 10/10 8,883 MiB 0,000 s OK
#10 [več] 10/10 8,836 MiB 0,000 s OK

Ocenjevani program (barvanje.py):
children = {}
parent = {}

# Read tree
N = int(input())
for i in range(N):
    chld = [c-1 for c in map(int,input().split()) if c!=0]
    children[i] = chld
    for c in chld:
        parent[c] = i

# Find root
root = 0
while root in parent:
    root = parent[root]

# Levels list
levels = [[root]]
while True:
    nodes_prev = levels[-1]
    nodes = []
    for i in nodes_prev:
        nodes += children[i]

    if len(nodes) == 0:
        break

    levels.append(nodes)

# Color with greedy
color = {}
for l in levels:
    for i in range(len(l)):
        limits = []
        if l[i] in parent:
            limits.append(color[parent[l[i]]])
        if i>0:
            limits.append(color[l[i-1]])
        for c in [1,2,3]:
            if c not in limits:
                color[l[i]] = c
                break

colors = [str(color[i]) for i in range(N)]
print(" ".join(colors))