結果
問題 |
No.479 頂点は要らない
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()