結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int fa[100009], siz[100009];

int get(int x){
	if (x==fa[x])	return x;
	return fa[x]=get(fa[x]);
}

void merge(int x, int y){
	x=get(x); y=get(y);
	if (x==y)	return ;
	fa[x]=y;
	siz[y]+=siz[x];
}

int cnt[100009];
int dp[100009];

int main(){
	for (int i=1; i<=100000; i++)	fa[i]=i, siz[i]=1;
	memset(dp, 0x3f, sizeof dp);
	dp[0]=0;
	
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		merge(u, v);
	}
	
	for (int i=1; i<=n; i++)
		if (fa[i]==i)
			cnt[siz[i]]++;
	
	for (int i=1; i<=n; i++){// \sqrt(n)
		for (int j=0; j<=17; j++) // log(n)
			if (cnt[i]>=(1<<j)){ // ??? 
				cnt[i]-=(1<<j); // ???????????????? 
				for (int k=n; k>=(1<<j)*i; k--)
					dp[k]=min(dp[k], dp[k-(1<<j)*i]+(1<<j));
			}
		if (cnt[i]>0){
			for (int k=n; k>=cnt[i]*i; k--)
				dp[k]=min(dp[k], dp[k-cnt[i]*i]+cnt[i]);
		}
	}
	
	for (int i=1; i<=n; i++)
		if (dp[i]<1e9)
			printf("%d\n", dp[i]-1);
		else
			printf("-1\n");
	return 0;
} // dffsddfsahsdfafdffjkdfdfjkfkfa
0