結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー | McGregorsh |
提出日時 | 2023-03-18 22:18:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 692 ms / 2,000 ms |
コード長 | 1,870 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 81,840 KB |
実行使用メモリ | 289,408 KB |
最終ジャッジ日時 | 2023-10-18 17:35:00 |
合計ジャッジ時間 | 18,215 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 149 ms
88,456 KB |
testcase_01 | AC | 149 ms
88,460 KB |
testcase_02 | AC | 150 ms
88,460 KB |
testcase_03 | AC | 148 ms
88,460 KB |
testcase_04 | AC | 150 ms
88,464 KB |
testcase_05 | AC | 155 ms
88,460 KB |
testcase_06 | AC | 150 ms
88,460 KB |
testcase_07 | AC | 150 ms
88,460 KB |
testcase_08 | AC | 153 ms
88,460 KB |
testcase_09 | AC | 151 ms
88,464 KB |
testcase_10 | AC | 151 ms
88,456 KB |
testcase_11 | AC | 394 ms
146,716 KB |
testcase_12 | AC | 394 ms
147,244 KB |
testcase_13 | AC | 353 ms
144,884 KB |
testcase_14 | AC | 391 ms
153,856 KB |
testcase_15 | AC | 692 ms
289,408 KB |
testcase_16 | AC | 339 ms
121,220 KB |
testcase_17 | AC | 329 ms
120,364 KB |
testcase_18 | AC | 150 ms
88,464 KB |
testcase_19 | AC | 407 ms
143,980 KB |
testcase_20 | AC | 340 ms
138,844 KB |
testcase_21 | AC | 412 ms
140,540 KB |
testcase_22 | AC | 397 ms
143,184 KB |
testcase_23 | AC | 413 ms
141,868 KB |
testcase_24 | AC | 400 ms
141,604 KB |
testcase_25 | AC | 424 ms
141,604 KB |
testcase_26 | AC | 446 ms
142,124 KB |
testcase_27 | AC | 410 ms
144,764 KB |
testcase_28 | AC | 391 ms
142,656 KB |
testcase_29 | AC | 407 ms
143,708 KB |
testcase_30 | AC | 438 ms
141,076 KB |
testcase_31 | AC | 408 ms
143,716 KB |
testcase_32 | AC | 410 ms
141,600 KB |
testcase_33 | AC | 393 ms
141,600 KB |
testcase_34 | AC | 386 ms
140,280 KB |
testcase_35 | AC | 437 ms
141,340 KB |
testcase_36 | AC | 435 ms
141,064 KB |
testcase_37 | AC | 407 ms
141,872 KB |
testcase_38 | AC | 348 ms
138,848 KB |
testcase_39 | AC | 343 ms
140,668 KB |
ソースコード
import sys, re from fractions import Fraction from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce from decimal import Decimal, getcontext, ROUND_HALF_UP def i_input(): return int(input()) def i_map(): return map(int, input().split()) def i_list(): return list(i_map()) def i_row(N): return [i_input() for _ in range(N)] def i_row_list(N): return [i_list() for _ in range(N)] def s_input(): return input() def s_map(): return input().split() def s_list(): return list(s_map()) def s_row(N): return [s_input for _ in range(N)] def s_row_str(N): return [s_list() for _ in range(N)] def s_row_list(N): return [list(s_input()) for _ in range(N)] def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 def main(): def dfs(s, p): for i in nums[s]: if i == p: continue dfs(i, s) if A[i] == 0: ans.append(1) A[i] = 1 A[s] = not A[s] N = int(input()) nums = [[] for i in range(N)] for i in range(N-1): a, b = i_map() a -= 1 b -= 1 nums[a].append(b) nums[b].append(a) A = i_list() cost = A.count(0) if cost % 2 == 1: print(-1) exit() ans = [] dfs(0, -1) print(sum(ans)) if __name__ == '__main__': main()