結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2015-12-10 13:45:28 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,154 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 33,088 KB |
最終ジャッジ日時 | 2024-09-15 07:29:12 |
合計ジャッジ時間 | 10,220 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 g = [[] for i in xrange(n1)] for i in xrange(m): u, v = inputs() g[u].append(v) g[v].append(u) ct = Counter() deq = deque() clear = deq.clear pop = deq.pop popleft = deq.popleft append = deq.append used = [1]+[0]*n for i in xrange(n1): if not used[i]: used[i] = 1 cnt = 1 append(i) while deq: v = popleft() for t in g[v]: if not used[t]: used[t] = 1 append(t) cnt += 1 ct[cnt] += 1 dp = [-1]+[n]*n for i, c in ct.items(): for a in xrange(i): clear() for j in xrange((n-a)/i+1): idx = j*i+a 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")