Rezultati

Up. imeNalogaJezikRezultatČas oddaje
zerodays-2019 Barvanje drevesa Python 3 0/100Napačen odgovor (WA) 24. apr '19 @ 18:55

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 9,867 MiB 0,000 s OK
#2 [več] 10/10 9,875 MiB 0,000 s OK
#3 [več] 10/10 9,793 MiB 0,000 s OK
#4 [več] 10/10 9,801 MiB 0,000 s OK
#5 [več] 10/10 9,875 MiB 0,000 s OK
#6 [več] 0/10 10,789 MiB 0,000 s Napačen odgovor
#7 [več] 0/10 10,922 MiB 0,000 s Napačen odgovor
#8 [več] 10/10 11,375 MiB 0,000 s OK
#9 [več] 10/10 11,219 MiB 0,000 s OK
#10 [več] 0/10 10,938 MiB 0,000 s Napačen odgovor

Ocenjevani program (barvanje.py):
from collections import defaultdict, deque

class Node():
    def __init__(self, i, levi, desni):
        self.i = i
        self.levi = levi
        self.desni = desni
        self.has_parent = False
        self.fiz_levi = None
        self.fiz_desni = None
        self.parent = None

    def __str__(self):
        return 'i: {}, levi: {}, desni: {}, fiz_levi: {}, fiz_desni: {}'.format(self.i, self.levi, self.desni, self.fiz_levi, self.fiz_desni)

N = int(input())
nodes = [Node(i, None, None) for i in range(N + 1)]
for i in range(1, N+1, 1):
    levi, desni = map(int, input().split())
    if levi != 0:
        nodes[i].levi = levi
        nodes[levi].has_parent = True
    if desni != 0:
        nodes[i].desni = desni
        nodes[desni].has_parent = True

# find root
root = -1
for node in nodes[1:]:
    if not node.has_parent:
        root = node.i
        break

globine = [[] for i in range(N)]
depth = 0
def poisci(globina, node):
    global depth, globine
    globine[globina].append(node.i)

    if node.levi is not None:
        poisci(globina + 1, nodes[node.levi])
    if node.desni is not None:
        poisci(globina + 1, nodes[node.desni])
    
    if depth < globina:
        depth = globina

poisci(0, nodes[root])

graf = defaultdict(set)

for nivo in range(len(globine)):
    for i in range(len(globine[nivo])):
        trenutn = nodes[globine[nivo][i]]

        if trenutn.levi is not None:
            graf[trenutn.i].add(trenutn.levi)
            graf[trenutn.levi].add(trenutn.i)
        if trenutn.desni is not None:
            graf[trenutn.i].add(trenutn.desni)
            graf[trenutn.desni].add(trenutn.i)
        
        if i != 0:
            graf[globine[nivo][i - 1]].add(trenutn.i)
            graf[trenutn.i].add(globine[nivo][i-1])
        if i <= len(globine[nivo]) - 2:
            graf[trenutn.i].add(globine[nivo][i+1])
            graf[globine[nivo][i+1]].add(trenutn.i)

q = deque()
q.append(root)
barve = defaultdict(int)
while len(q):
    trenutn = q.popleft()
    zasedene = set()
    for sosed in graf[trenutn]:
        if barve[sosed] > 0:
            zasedene.add(barve[sosed])
        else:
            q.append(sosed)
    
    barva = 1
    while barva in zasedene:
        barva += 1
    
    barve[trenutn] = barva

for i in range(1, N+1):
    if i != 1:
        print(' ', end='')
    print(barve[i], end='')
print()