結果
問題 | No.912 赤黒木 |
ユーザー | maspy |
提出日時 | 2020-04-22 18:22:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 821 ms / 3,000 ms |
コード長 | 1,414 bytes |
コンパイル時間 | 209 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 155,496 KB |
最終ジャッジ日時 | 2024-04-20 03:31:28 |
合計ジャッジ時間 | 18,436 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
53,592 KB |
testcase_01 | AC | 32 ms
53,504 KB |
testcase_02 | AC | 52 ms
70,288 KB |
testcase_03 | AC | 61 ms
72,936 KB |
testcase_04 | AC | 46 ms
66,400 KB |
testcase_05 | AC | 56 ms
69,920 KB |
testcase_06 | AC | 56 ms
70,408 KB |
testcase_07 | AC | 60 ms
73,032 KB |
testcase_08 | AC | 41 ms
61,804 KB |
testcase_09 | AC | 51 ms
68,436 KB |
testcase_10 | AC | 43 ms
63,848 KB |
testcase_11 | AC | 50 ms
69,024 KB |
testcase_12 | AC | 789 ms
147,904 KB |
testcase_13 | AC | 813 ms
150,144 KB |
testcase_14 | AC | 808 ms
145,884 KB |
testcase_15 | AC | 791 ms
150,420 KB |
testcase_16 | AC | 806 ms
147,608 KB |
testcase_17 | AC | 817 ms
149,240 KB |
testcase_18 | AC | 789 ms
146,344 KB |
testcase_19 | AC | 775 ms
144,536 KB |
testcase_20 | AC | 736 ms
143,992 KB |
testcase_21 | AC | 735 ms
143,756 KB |
testcase_22 | AC | 759 ms
154,712 KB |
testcase_23 | AC | 734 ms
155,496 KB |
testcase_24 | AC | 759 ms
155,228 KB |
testcase_25 | AC | 792 ms
148,200 KB |
testcase_26 | AC | 821 ms
150,492 KB |
testcase_27 | AC | 784 ms
147,180 KB |
testcase_28 | AC | 791 ms
147,544 KB |
testcase_29 | AC | 760 ms
147,028 KB |
testcase_30 | AC | 807 ms
147,516 KB |
testcase_31 | AC | 745 ms
143,796 KB |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import itertools N = int(readline()) graph = [[] for _ in range(N + 1)] for _ in range(N - 1): a, b = map(int, readline().split()) graph[a].append(b) graph[b].append(a) deg = [0] * (N + 1) for _ in range(N - 1): a, b = map(int, readline().split()) deg[a] += 1 deg[b] += 1 root = 1 parent = [0] * (N + 1) order = [] stack = [root] while stack: x = stack.pop() order.append(x) for y in graph[x]: if y == parent[x]: continue parent[y] = x stack.append(y) INF = 10 ** 9 dp = [[0, INF, INF, INF, INF, INF] for _ in range(N + 1)] for v in order[::-1]: a, b, c, d, e, f = dp[v] if deg[v] & 1: dp[v] = [ d, min(a, e), min(b, f), a + 1, min(b, d) + 1, min(c, e) + 1 ] else: dp[v] = [ a, min(b, d), min(c, e), d + 1, min(a, e) + 1, min(b, f) + 1 ] if v == root: break p = parent[v] A = [INF, INF, INF, INF, INF, INF] for a, b in itertools.product(range(6), repeat=2): i, k = divmod(a, 3) j, l = divmod(b, 3) i ^= j k += l if k > 2: continue c = 3 * i + k A[c] = min(A[c], dp[v][a] + dp[p][b]) dp[p] = A x = min(dp[root][:3]) print(N - 1 + x)