提出 #53284820

ソースコード 拡げる

N, M = map(int, input().split())
g = [0]*N
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    # g[x] := x -> y に行ける集合
    g[x] |= (1 << y)

dp = [0]*(1 << N)
dp[0] = 1
for s in range(1 << N):
    for j in range(N):
        # まだ集合 S に j がいない かつ j -> s に行く道が存在しない
        if not (s >> j) & 1 and not (s & g[j]):
            dp[s | (1 << j)] += dp[s]

print(dp[(1 << N) - 1])

提出情報

提出日時
問題 D - 徒競走
ユーザ ryusuke_h
言語 Python (PyPy 3.10-v7.3.12)
得点 100
コード長 467 Byte
結果 AC
実行時間 75 ms
メモリ 81912 KiB

ジャッジ結果

セット名 Sample Subtask1 All
得点 / 配点 0 / 0 30 / 30 70 / 70
結果
AC × 3
AC × 15
AC × 32
セット名 テストケース
Sample 0_00.txt, 0_01.txt, 0_02.txt
Subtask1 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt
ケース名 結果 実行時間 メモリ
0_00.txt AC 57 ms 75936 KiB
0_01.txt AC 57 ms 75964 KiB
0_02.txt AC 72 ms 81536 KiB
1_00.txt AC 56 ms 76100 KiB
1_01.txt AC 59 ms 80896 KiB
1_02.txt AC 60 ms 81012 KiB
1_03.txt AC 61 ms 81456 KiB
1_04.txt AC 60 ms 80992 KiB
1_05.txt AC 57 ms 76360 KiB
1_06.txt AC 56 ms 76272 KiB
1_07.txt AC 57 ms 76380 KiB
1_08.txt AC 58 ms 76228 KiB
1_09.txt AC 61 ms 80900 KiB
1_10.txt AC 61 ms 81004 KiB
1_11.txt AC 60 ms 80964 KiB
1_12.txt AC 61 ms 81116 KiB
2_00.txt AC 72 ms 81664 KiB
2_01.txt AC 73 ms 81560 KiB
2_02.txt AC 73 ms 81712 KiB
2_03.txt AC 74 ms 81696 KiB
2_04.txt AC 67 ms 81640 KiB
2_05.txt AC 66 ms 81504 KiB
2_06.txt AC 67 ms 81432 KiB
2_07.txt AC 67 ms 81364 KiB
2_08.txt AC 73 ms 81860 KiB
2_09.txt AC 73 ms 81720 KiB
2_10.txt AC 73 ms 81680 KiB
2_11.txt AC 73 ms 81912 KiB
2_12.txt AC 73 ms 81780 KiB
2_13.txt AC 72 ms 81884 KiB
2_14.txt AC 73 ms 81832 KiB
2_15.txt AC 75 ms 81672 KiB