結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2015-12-10 14:08:14 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,145 bytes |
コンパイル時間 | 98 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 23,388 KB |
最終ジャッジ日時 | 2024-09-15 07:30:53 |
合計ジャッジ時間 | 9,274 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 TLE * 2 -- * 31 |
ソースコード
from collections import deque, Counter from sys import stdin, stdout readline = stdin.readline inputs = lambda: map(int, readline().split()) n, m = inputs() n1 = n+1 ct = Counter() parent = [1] + range(1,n1) count = [1]*n1 def root(x): p = parent[x] if x!=p: parent[x] = x = root(p) return x for i in xrange(m): u, v = inputs() a = root(u); b = root(v) if a!=b: if a<b: parent[b] = a count[a] += count[b] else: parent[a] = b count[b] += count[a] for i, c in enumerate(count): if i==root(i): ct[count[i]] += 1 deq = deque() clear = deq.clear pop = deq.pop popleft = deq.popleft append = deq.append dp = [-1]+[n]*n for i, c in ct.items(): for a in xrange(i): clear() for j, idx in enumerate(range(a, n1, i)): p = (dp[idx]-j, -j) while deq and p <= deq[-1]: pop() append(p) v, u = deq[0] dp[idx] = v + j if c==j+u: popleft() dp = [v if v!=n else -1 for v in dp] stdout.write("\n".join(map(str, dp[1:])) + "\n")