結果
問題 | No.1227 I hate ThREE |
ユーザー | tyawanmusi |
提出日時 | 2020-07-28 21:22:20 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,037 ms / 2,000 ms |
コード長 | 1,089 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 11,124 KB |
実行使用メモリ | 157,884 KB |
最終ジャッジ日時 | 2023-08-30 14:25:34 |
合計ジャッジ時間 | 13,583 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
8,168 KB |
testcase_01 | AC | 16 ms
8,364 KB |
testcase_02 | AC | 16 ms
8,396 KB |
testcase_03 | AC | 32 ms
9,824 KB |
testcase_04 | AC | 29 ms
9,148 KB |
testcase_05 | AC | 60 ms
10,248 KB |
testcase_06 | AC | 16 ms
8,340 KB |
testcase_07 | AC | 17 ms
8,268 KB |
testcase_08 | AC | 112 ms
12,164 KB |
testcase_09 | AC | 87 ms
10,028 KB |
testcase_10 | AC | 58 ms
9,844 KB |
testcase_11 | AC | 386 ms
22,636 KB |
testcase_12 | AC | 859 ms
36,180 KB |
testcase_13 | AC | 24 ms
8,768 KB |
testcase_14 | AC | 74 ms
10,696 KB |
testcase_15 | AC | 121 ms
14,796 KB |
testcase_16 | AC | 149 ms
16,260 KB |
testcase_17 | AC | 172 ms
17,772 KB |
testcase_18 | AC | 412 ms
31,288 KB |
testcase_19 | AC | 316 ms
26,728 KB |
testcase_20 | AC | 447 ms
32,868 KB |
testcase_21 | AC | 17 ms
8,096 KB |
testcase_22 | AC | 168 ms
17,928 KB |
testcase_23 | AC | 1,019 ms
157,884 KB |
testcase_24 | AC | 1,037 ms
96,536 KB |
testcase_25 | AC | 551 ms
86,272 KB |
testcase_26 | AC | 700 ms
41,324 KB |
testcase_27 | AC | 735 ms
41,672 KB |
testcase_28 | AC | 381 ms
30,120 KB |
testcase_29 | AC | 755 ms
42,016 KB |
testcase_30 | AC | 361 ms
28,836 KB |
testcase_31 | AC | 357 ms
28,648 KB |
testcase_32 | AC | 748 ms
41,708 KB |
testcase_33 | AC | 354 ms
28,500 KB |
testcase_34 | AC | 732 ms
41,476 KB |
testcase_35 | AC | 349 ms
27,872 KB |
ソースコード
import sys sys.setrecursionlimit(2000) input = sys.stdin.readline def solve(x): minc = min(2 * n - 1, x) dp = [minc * [1] for _ in range(n)] def dfs(r, node): for mode in edge[node]: if mode == r:continue dpsub = dfs(node, mode) dp[node][0] = (dp[node][0] * dpsub[1]) % mod dp[node][minc - 1] = (dp[node][minc - 1] * dpsub[minc - 2]) % mod for i in range(1, minc - 1): dp[node][i] = (dp[node][i] * (dpsub[i - 1]+dpsub[i + 1])) % mod return dp[node] lastdp = dfs(-1, 0) if minc == x: return sum(lastdp) else: return sum(lastdp) + (x - minc) * lastdp[minc // 2] mod = 10 ** 9 + 7 n, c = map(int, input().split()) edge = [[] for _ in range(n)] for _ in range(n - 1): a, b = map(int, input().split()) a -= 1 b -= 1 edge[a].append(b) edge[b].append(a) c1 = (c + 2) // 3 c2 = (c + 1) // 3 c3 = c // 3 ans1 = solve(c1) if c1 == c2: ans2 = ans1 elif c2 == 1: ans2 = 0 else: ans2 = solve(c2) if c2 == c3: ans3 = ans2 elif c3 == 1: ans3 = 0 else: ans3 = solve(c3) print((ans1 + ans2 + ans3) % mod)