結果

問題 No.479 頂点は要らない
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:52:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,809 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 111,588 KB
最終ジャッジ日時 2025-03-26 15:53:04
合計ジャッジ時間 5,791 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1

    edges = [[] for _ in range(n)]
    for _ in range(m):
        a = int(input[idx])
        idx += 1
        b = int(input[idx])
        idx += 1
        if a > b:
            a, b = b, a
        edges[a].append(b)
        edges[b].append(a)

    selected = [False] * n

    # Initialize selected with all the u of each edge (u, v)
    for u in range(n):
        for v in edges[u]:
            if u < v:
                selected[u] = True

    # Iterate vertices from largest to smallest
    for i in reversed(range(n)):
        if not selected[i]:
            continue
        can_remove = True
        # Check all adjacent edges
        for j in edges[i]:
            if j < i:
                # This edge is stored in the j's list as u, but here i is the larger one
                # The edge is (j, i), so if j is not selected, then i must be kept
                if not selected[j]:
                    can_remove = False
                    break
            else:
                # The edge is (i, j), where i is the smaller one. But since we are processing i in reverse order, j could be larger.
                # Since i was initially selected as the smaller vertex, but if we remove i, we need to check if j is selected.
                if not selected[j]:
                    can_remove = False
                    break
        if can_remove:
            selected[i] = False

    # Calculate the sum
    total = 0
    for i in range(n):
        if selected[i]:
            total += (1 << i)

    # Convert to binary
    if total == 0:
        print("0")
    else:
        print(bin(total)[2:])
    print()

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