제출 #986216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986216		dorjderem	The Xana coup (BOI21_xanadu)	Pypy 3	0 / 100	1071 ms	334608 KiB

xanadu

from collections import defaultdict
import sys

n = int(input())
mp = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    mp[a-1].append(b-1)
    mp[b-1].append(a-1)
a = list(map(int,input().split()))
for i in range(n):
    a[i] = True if a[i] == 1 else False

can = False
for i in range(n):
    q = []
    q.append([i, a])
    level = 0
    while q:
        l = len(q)
        for _ in range(l):
            top = q.pop(0)
            if not any(top[1]):
                can = True
                print(level)
                sys.exit()
            cp = top[1][:]
            cp[top[0]] = not cp[top[0]]
            for nxt in mp[top[0]]:
                cp[nxt] = not cp[nxt]
            for j in range(n):
                if j != top[0]:
                    q.append([j, cp])
        level += 1
        if level >= 20:
            break
if not can:
    print("IMPOSSIBLE")

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30