結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2015-12-16 01:47:52 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 1,405 ms / 2,000 ms |
コード長 | 1,113 bytes |
コンパイル時間 | 1,856 ms |
コンパイル使用メモリ | 76,820 KB |
実行使用メモリ | 124,964 KB |
最終ジャッジ日時 | 2024-09-16 05:27:57 |
合計ジャッジ時間 | 26,998 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
from collections import deque, Counter from sys import stdin, stdout ss = [map(int, s.split()) for s in stdin.readlines()] n, m = ss[0] n1 = n+1 g = [[] for i in xrange(n1)] for u, v in ss[1:]: 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")