結果

問題 No.317 辺の追加
コンテスト
ユーザー Tawara
提出日時 2015-12-12 17:24:39
言語 PyPy2
(7.3.20)
コンパイル:
pypy2 -m py_compile _filename_
実行:
/usr/bin/pypy2 Main.pyc
結果
AC  
実行時間 291 ms / 2,000 ms
コード長 443 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,440 ms
コンパイル使用メモリ 80,768 KB
実行使用メモリ 102,272 KB
最終ジャッジ日時 2026-05-29 14:47:19
合計ジャッジ時間 13,826 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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