結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2025-01-19 11:40:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 1,174 bytes
コンパイル時間 1,874 ms
コンパイル使用メモリ 194,264 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-19 11:40:29
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
inline long long read(){
	long long x=0; char ch; bool f=0;
	while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
	if(ch=='-') f=1;
	else x=ch^48;
	while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
const int N=1e5+5,B=333;
int n,fa[N],sz[N];
int get(int x){
	return x==fa[x]?x:fa[x]=get(fa[x]);
}
int c[N],f[N];
int main(){
	n=read(); int m=read();
	for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
	while(m--){
		int x=read(),y=read();
		x=get(x),y=get(y);
		if(x==y) continue;
		if(sz[x]>sz[y]) swap(x,y);
		sz[y]+=sz[x],fa[x]=y;
	}
	for(int i=1;i<=n;i++) f[i]=1e9;
	for(int i=1;i<=n;i++){
		if(get(i)==i) c[sz[i]]++;
	}
	f[0]=0;
	for(int i=1;i<=n;i++){
		if(i>B){
			while(c[i]--){
				for(int j=n;j>=i;j--) f[j]=min(f[j],f[j-i]+1); 
			}
		}
		else{
			for(int j=1;c[i]>=j;j=j*2){
				c[i]-=j;
				for(int t=n;t>=j*i;t--) f[t]=min(f[t],f[t-j*i]+j);
			}
			if(c[i]){
				for(int t=n;t>=c[i]*i;t--) f[t]=min(f[t],f[t-c[i]*i]+c[i]);
			}
		}
//		cerr<<i<<": ";
//		for(int j=1;j<=n;j++) cout<<f[j]<<" "; puts("");
	}
	for(int i=1;i<=n;i++){
		if(f[i]<=n) printf("%d\n",f[i]-1);
		else puts("-1");
	}
	return 0;
}
0