Submission #66695

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from typing import List
def main():
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
assert 1 <= N <= 12
assert 1 <= P <= 10**9
G: List[List[int]] = [[] for _ in range(N)]
costs = [0] * N
for i in range(1, N):
p, k, *s = map(int, input().split())
assert 1 <= p <= 10**9
assert 1 <= k <= N - 1
assert len(s) == k
assert all(1 <= s_i <= N and s_i != (i + 1) for s_i in s)
costs[i] = p
for u in s:
u -= 1
G[u].append(i)
ans = 0
for bits in range(1, 1 << N):
cost_sum = 0
visited = [False] * N
stack = [0]
while stack:
u = stack.pop()
if visited[u]:
continue
visited[u] = True
cost_sum += costs[u]
stack.extend(nxt for nxt in G[u] if (bits >> nxt & 1) and not visited[nxt])
if cost_sum <= P:
ans = max(ans, sum(visited))
print(ans)
main()

ステータス

項目 データ
問題 1510 - Skill Tree
ユーザー名 syoribu
投稿日時 2021-05-15 03:02:12
言語 Python3
状態 Accepted
得点 3
ソースコード長 1062 Byte
最大実行時間 131 ms
最大メモリ使用量 5048 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 58 ms 4700 KB
1
in02.txt AC 95 ms 4888 KB
1
in03.txt AC 52 ms 4676 KB
1
in04.txt AC 51 ms 4736 KB
1
in05.txt AC 56 ms 4784 KB
1
in06.txt AC 94 ms 4828 KB
1
in07.txt AC 109 ms 4868 KB
1
in08.txt AC 97 ms 4908 KB
1
in09.txt AC 109 ms 4952 KB
1
in10.txt AC 97 ms 4736 KB
1
in11.txt AC 99 ms 4780 KB
1
in12.txt AC 73 ms 4828 KB
1
in13.txt AC 72 ms 4872 KB
1
in14.txt AC 74 ms 4912 KB
1
in15.txt AC 78 ms 4692 KB
1
in16.txt AC 122 ms 4732 KB
1
in17.txt AC 131 ms 4780 KB
1
in18.txt AC 77 ms 4832 KB
1
in19.txt AC 69 ms 4744 KB
1
in20.txt AC 69 ms 4788 KB
1
in21.txt AC 82 ms 4820 KB
1
in22.txt AC 89 ms 4724 KB
1
in23.txt AC 84 ms 4760 KB
1
in24.txt AC 81 ms 4792 KB
1
in25.txt AC 84 ms 4812 KB
1
in26.txt AC 85 ms 4852 KB
1
in27.txt AC 100 ms 4880 KB
1
in28.txt AC 127 ms 4920 KB
1
in29.txt AC 124 ms 4840 KB
1
in30.txt AC 66 ms 4756 KB
1
in31.txt AC 104 ms 4792 KB
1
in32.txt AC 107 ms 4824 KB
1
in33.txt AC 46 ms 4992 KB
1
in34.txt AC 54 ms 4912 KB
1
in35.txt AC 54 ms 4836 KB
1
in36.txt AC 56 ms 4876 KB
1
in37.txt AC 54 ms 5048 KB
1
sample01.txt AC 51 ms 4968 KB
1
sample02.txt AC 63 ms 5012 KB
1