Submission #19103577

Source Code Expand

N, M = map(int, input().split())
G = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    G[A] |= 1 << B
    G[B] |= 1 << A

dp = [0xff] * (1 << N)
dp[0] = 1
for i in range(N):
    for j in range(1 << N):
        if dp[j] == 1 and (G[i] & j) == j:
            dp[j | 1 << i] = 1

for i in range(1 << N):
    j = i
    while j:
        if dp[i] > dp[j] + dp[i ^ j]:
            dp[i] = dp[j] + dp[i ^ j]
        j -= 1
        j &= i

print(dp[-1])

Submission Info

Submission Time
Task F - Close Group
User tatyam
Language PyPy3 (7.3.0)
Score 600
Code Size 484 Byte
Status AC
Exec Time 1152 ms
Memory 69880 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status AC
AC × 44
Set Name Test Cases
Sample
All 01_sample.txt, 02_sample.txt, 03_sample.txt, 04_sample.txt, 05_tiny.txt, 06_tiny.txt, 07_tiny.txt, 08_tiny.txt, 09_tiny.txt, 10_tiny.txt, 11_tiny.txt, 12_small.txt, 13_small.txt, 14_small.txt, 15_small.txt, 16_small.txt, 17_small.txt, 18_small.txt, 19_small.txt, 20_small.txt, 21_small.txt, 22_small.txt, 23_small.txt, 24_small.txt, 25_small.txt, 26_small.txt, 27_large.txt, 28_large.txt, 29_large.txt, 30_large.txt, 31_large.txt, 32_large.txt, 33_large.txt, 34_large.txt, 35_large.txt, 36_large.txt, 37_large.txt, 38_large.txt, 39_large.txt, 40_large.txt, 41_large.txt, 42_max.txt, 43_max.txt, 44_max.txt
Case Name Status Exec Time Memory
01_sample.txt AC 74 ms 61524 KiB
02_sample.txt AC 55 ms 61696 KiB
03_sample.txt AC 66 ms 67596 KiB
04_sample.txt AC 1018 ms 69720 KiB
05_tiny.txt AC 65 ms 61476 KiB
06_tiny.txt AC 55 ms 61460 KiB
07_tiny.txt AC 52 ms 61660 KiB
08_tiny.txt AC 53 ms 61628 KiB
09_tiny.txt AC 54 ms 61668 KiB
10_tiny.txt AC 53 ms 61552 KiB
11_tiny.txt AC 53 ms 61500 KiB
12_small.txt AC 55 ms 61628 KiB
13_small.txt AC 58 ms 63476 KiB
14_small.txt AC 54 ms 61696 KiB
15_small.txt AC 54 ms 61684 KiB
16_small.txt AC 53 ms 61960 KiB
17_small.txt AC 53 ms 61836 KiB
18_small.txt AC 57 ms 63272 KiB
19_small.txt AC 57 ms 63536 KiB
20_small.txt AC 54 ms 61936 KiB
21_small.txt AC 58 ms 63328 KiB
22_small.txt AC 56 ms 63528 KiB
23_small.txt AC 56 ms 61568 KiB
24_small.txt AC 55 ms 63468 KiB
25_small.txt AC 52 ms 61708 KiB
26_small.txt AC 55 ms 61676 KiB
27_large.txt AC 1134 ms 69700 KiB
28_large.txt AC 115 ms 67460 KiB
29_large.txt AC 160 ms 67720 KiB
30_large.txt AC 70 ms 67540 KiB
31_large.txt AC 341 ms 68528 KiB
32_large.txt AC 910 ms 69804 KiB
33_large.txt AC 918 ms 69880 KiB
34_large.txt AC 928 ms 69436 KiB
35_large.txt AC 1152 ms 69832 KiB
36_large.txt AC 929 ms 69464 KiB
37_large.txt AC 353 ms 68684 KiB
38_large.txt AC 68 ms 67612 KiB
39_large.txt AC 57 ms 65792 KiB
40_large.txt AC 66 ms 67564 KiB
41_large.txt AC 67 ms 67584 KiB
42_max.txt AC 915 ms 69640 KiB
43_max.txt AC 920 ms 69456 KiB
44_max.txt AC 932 ms 69584 KiB