Submission #18240136


Source Code Expand

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)))

Submission Info

Submission Time
Task G - Mixture Drug
User toyuzuko
Language PyPy3 (7.3.0)
Score 600
Code Size 1955 Byte
Status AC
Exec Time 1169 ms
Memory 110228 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 51
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
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