結果

問題 No.317 辺の追加
ユーザー Tawara
提出日時 2015-12-12 17:24:39
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 467 ms / 2,000 ms
コード長 443 bytes
コンパイル時間 2,093 ms
コンパイル使用メモリ 76,712 KB
実行使用メモリ 98,088 KB
最終ジャッジ日時 2024-12-23 14:39:05
合計ジャッジ時間 16,696 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict as D
I=int;f=lambda:map(I,raw_input().split());R=range;N,M=f();P=R(N+1)
def r(x):
	while x^P[x]:P[x]=x=P[P[x]]
	return x
Cc=D(I);Cn=D(I);A=[N]*(N+1);A[0]=0
for i in R(M):u,v=map(r,f());P[u]=v
for i in R(N):Cc[r(i+1)]+=1
for v in Cc.values():Cn[v]+=1
for v,n in Cn.items():
	m=1
	while n>0:
		m=min(m,n);w=v*m
		for j in R(N,w-1,-1):A[j]=min(A[j],A[j-w]+m)
		n-=m;m*=2
for i in R(N):print A[i+1]*(A[i+1]<N)-1
0