結果
問題 | No.1194 Replace |
ユーザー |
|
提出日時 | 2020-08-22 17:44:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 849 ms / 2,000 ms |
コード長 | 781 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 217,472 KB |
最終ジャッジ日時 | 2024-10-15 11:30:15 |
合計ジャッジ時間 | 15,006 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import sys input = sys.stdin.readline from collections import * def bfs(s): if ma[s]!=-1: return q = deque([s]) ma[s] = s while q: v = q.popleft() for nv in G[v]: if ma[nv]==-1: ma[nv] = s q.append(nv) N, M = map(int, input().split()) BC = [tuple(map(int, input().split())) for _ in range(M)] l = [] for B, C in BC: l.append(B-1) l.append(C-1) l = list(set(l)) l.sort() idx = defaultdict(int) for i in range(len(l)): idx[l[i]] = i G = [[] for _ in range(len(l))] for B, C in BC: G[idx[C-1]].append(idx[B-1]) ma = [-1]*len(l) for i in range(len(l)-1, -1, -1): bfs(i) ans = N*(N+1)//2 for li in l: ans -= li ans += l[ma[idx[li]]] print(ans)