結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー |
|
提出日時 | 2023-02-06 15:16:14 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 935 ms / 2,000 ms |
コード長 | 1,246 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 76,016 KB |
最終ジャッジ日時 | 2024-07-04 19:22:23 |
合計ジャッジ時間 | 25,742 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
def main():N = int(input())graphs = [[] for _ in range(N)]for _ in range(N-1):dep, dest = map(lambda n: int(n)-1, input().split())graphs[dep].append(dest)graphs[dest].append(dep)color = list(map(int, input().split()))if color.count(0) % 2:print(-1)returnmoved = set()searched = set()stack = []stack.append([0, None])moved.add(0)change_ctr = 0while stack:ctr_child = 0current_notice_node, notice_node_parent = stack[-1]for node_idx in graphs[current_notice_node]:if node_idx not in moved:stack.append((node_idx, current_notice_node))moved.add(node_idx)ctr_child += 1if ctr_child == 0:current_node_idx, parent_idx = stack.pop()if color[current_node_idx] == 0:if parent_idx is not None:color[current_node_idx] = 1color[parent_idx] ^= 1change_ctr += 1else:print(-1)returnsearched.add(current_node_idx)print(change_ctr)if __name__ == "__main__":main()