結果

問題 No.95 Alice and Graph
ユーザー しらっ亭しらっ亭
提出日時 2015-10-01 00:02:25
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 698 bytes
コンパイル時間 117 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 211,560 KB
最終ジャッジ日時 2024-07-19 18:44:59
合計ジャッジ時間 12,891 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    N, M, K = map(int, input().split())

    es = [set() for _ in range(N)]

    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        es[u].add(v)
        es[v].add(u)

    dp = {}

    def rec(p, c, k):
        pck = (p, c, k)

        if k == 0:
            return c

        if pck in dp:
            return dp[pck]

        ma = 0
        for n in es[p]:
            ma = max(ma, rec(n, c | (1 << n), k - 1))

        dp[pck] = ma
        return ma

    ab = rec(0, 0, K)

    ans = 0
    for i in range(N):
        if ab & 1 == 1:
            ans += 2 ** i - 1
        ab >>= 1

    print(ans)


if __name__ == '__main__':
    solve()
0