結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2026-02-03 10:39:10
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 238 ms / 2,000 ms
コード長 1,035 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 882 ms
コンパイル使用メモリ 83,616 KB
実行使用メモリ 8,288 KB
最終ジャッジ日時 2026-02-03 10:39:19
合計ジャッジ時間 8,902 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5,M=4e5+5,INF=1e9;
int n,m,tot=1,cnt;
int head[N],ver[M],Next[M],sz[N],f[N];
bool v[N];

void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

void dfs(int x){
	v[x]=1;
	sz[cnt]++; 
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(v[y]) continue;
		dfs(y);
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!v[i]){
			cnt++;
			dfs(i);
		}
		f[i]=INF;
	}
	sort(sz+1,sz+cnt+1);
	f[0]=0;
	for(int i=1,j;i<=cnt;i=j+1){
		j=i;
		while(j<cnt&&sz[i]==sz[j+1]) j++;
		int rest=j-i+1;
		for(int k=0;;k++){
			if(rest>=(1<<k)){
				for(int l=n;l>=(1<<k)*sz[i];l--) f[l]=min(f[l],f[l-(1<<k)*sz[i]]+(1<<k));
				rest-=(1<<k);
			}
			else{
				for(int l=n;l>=rest*sz[i];l--) f[l]=min(f[l],f[l-rest*sz[i]]+rest);
				break;
			}
		}
//		cout<<sz[i]<<' '<<j-i+1<<endl;
	}
	for(int i=1;i<=n;i++){
		if(f[i]==INF) puts("-1");
		else cout<<f[i]-1<<endl;
	}
	return 0;
}
0