ソースコード 拡げる

Copy
```def maximum_independent_set(n, edge):
n1 = n // 2
n2 = n - n1
maxlen = 0
res = 0

ind1 = [True] * (1 << n1)
ind2 = [True] * (1 << n2)
nc = [(1 << n2) - 1] * (1 << n1)
mis = [0] * (1 << n2)
mislen = [0] * (1 << n2)

for u, v in edge:
if u < n1 and v < n1:
ind1[1 << u | 1 << v] = False
elif u < n1:
nc[1 << u] ^= 1 << (v - n1)
elif v < n1:
nc[1 << v] ^= 1 << (u - n1)
else:
ind2[1 << (u - n1) | 1 << (v - n1)] = False

for bit in range(1 << n1):
if ind1[bit]: continue
for i in range(n1):
ind1[bit | 1 << i] = False

for bit in range(1 << n1):
for i in range(n1):
if (bit >> i) & 1: continue
nc[bit | 1 << i] = nc[bit] & nc[1 << i]

for bit in range(1 << n2):
if ind2[bit]: continue
for i in range(n2):
ind2[bit | 1 << i] = False

for bit in range(1 << n2):
if not ind2[bit]: continue
mis[bit] = bit
for i in range(n2):
if (bit >> i) & 1:
mislen[bit] += 1

for bit in range(1 << n2):
for i in range(n2):
if (bit >> i) & 1: continue
if mislen[bit | 1 << i] < mislen[bit]:
mislen[bit | 1 << i] = mislen[bit]
mis[bit | 1 << i] = mis[bit]

for bit in range(1 << n1):
tmp = 0
if not ind1[bit]: continue
for i in range(n1):
if (bit >> i) & 1:
tmp += 1
tmp += mislen[nc[bit]]
if maxlen < tmp:
maxlen = tmp
res = (mis[nc[bit]] << n1) + bit

res = [i for i in range(N) if (res >> i) & 1]
return res

N, M = map(int, input().split())
E = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

print(len(maximum_independent_set(N, E)))```

#### 提出情報

提出日時 2020-11-20 23:43:32+0900 G - Mixture Drug toyuzuko PyPy3 (7.3.0) 600 1955 Byte AC 1169 ms 110228 KB

#### ジャッジ結果

セット名 Sample All

 AC × 3
 AC × 51
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 72 ms 62288 KB
sample_02.txt AC 49 ms 62028 KB
sample_03.txt AC 78 ms 68652 KB
subtask_1_1.txt AC 53 ms 62216 KB
subtask_1_10.txt AC 1013 ms 109632 KB
subtask_1_11.txt AC 70 ms 62516 KB
subtask_1_12.txt AC 1150 ms 109408 KB
subtask_1_13.txt AC 754 ms 101388 KB
subtask_1_14.txt AC 1052 ms 109272 KB
subtask_1_15.txt AC 78 ms 68068 KB
subtask_1_16.txt AC 1024 ms 109184 KB
subtask_1_17.txt AC 1031 ms 109560 KB
subtask_1_18.txt AC 1120 ms 109996 KB
subtask_1_19.txt AC 98 ms 68596 KB
subtask_1_2.txt AC 1082 ms 109452 KB
subtask_1_20.txt AC 1138 ms 110104 KB
subtask_1_21.txt AC 1140 ms 109668 KB
subtask_1_22.txt AC 967 ms 110228 KB
subtask_1_23.txt AC 79 ms 68272 KB
subtask_1_24.txt AC 148 ms 71308 KB
subtask_1_25.txt AC 938 ms 110096 KB
subtask_1_26.txt AC 1034 ms 109728 KB
subtask_1_27.txt AC 952 ms 109824 KB
subtask_1_28.txt AC 1108 ms 109384 KB
subtask_1_29.txt AC 1091 ms 109756 KB
subtask_1_3.txt AC 208 ms 76760 KB
subtask_1_30.txt AC 53 ms 62352 KB
subtask_1_31.txt AC 75 ms 68084 KB
subtask_1_32.txt AC 75 ms 67988 KB
subtask_1_33.txt AC 118 ms 70504 KB
subtask_1_34.txt AC 997 ms 109548 KB
subtask_1_35.txt AC 1151 ms 109672 KB
subtask_1_36.txt AC 1021 ms 109860 KB
subtask_1_37.txt AC 1017 ms 109472 KB
subtask_1_38.txt AC 1135 ms 109740 KB
subtask_1_39.txt AC 1169 ms 109756 KB
subtask_1_4.txt AC 1150 ms 109588 KB
subtask_1_40.txt AC 1134 ms 109740 KB
subtask_1_41.txt AC 1129 ms 109484 KB
subtask_1_42.txt AC 1155 ms 110188 KB
subtask_1_43.txt AC 964 ms 109392 KB
subtask_1_44.txt AC 1099 ms 109768 KB
subtask_1_45.txt AC 1162 ms 109488 KB
subtask_1_46.txt AC 1066 ms 109628 KB
subtask_1_47.txt AC 1022 ms 109716 KB
subtask_1_48.txt AC 1116 ms 109944 KB
subtask_1_5.txt AC 263 ms 78772 KB
subtask_1_6.txt AC 1113 ms 109828 KB
subtask_1_7.txt AC 350 ms 85112 KB
subtask_1_8.txt AC 1020 ms 109740 KB
subtask_1_9.txt AC 424 ms 89364 KB