結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2025-01-19 11:39:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 62 ms / 2,000 ms
コード長 1,219 bytes
コンパイル時間 1,585 ms
コンパイル使用メモリ 164,348 KB
実行使用メモリ 15,872 KB
最終ジャッジ日時 2025-01-19 11:39:47
合計ジャッジ時間 5,363 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45)f=-1;
		c=getchar();
	}
	while(c<=57&&c>=48){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
void out(int x){
    if(x<0)putchar(45),x=-x;
    if(x<10)putchar(x+48);
    else out(x/10),putchar(x%10+48);
}
const int N=1e5+2;
bool s[N];
int n,m,g[N],a[N],tot,B[N];
int v[N],w[N],dd;
vector<int> G[N];

void dfs(int u,int fa){
	a[tot]++;
	s[u]=1;
	for(auto v:G[u]){
		if(v==fa||s[v])continue;
		dfs(v,u);
	}
}
signed main(){
	n=read();m=read();
	for(int i=1,u,v;i<=m;++i){
		u=read();v=read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;++i){
		if(s[i])continue;
		++tot;
		dfs(i,0);
		g[a[tot]]++;
	//	cout<<a[tot]<<" ";
	}
	for(int i=1;i<=n;++i){
		int qz=1;
		while(qz<=g[i]){
			++dd;
			v[dd]=qz*i;
			w[dd]=qz;
			g[i]-=qz;
			qz<<=1;
		}
		if(g[i]){
			++dd;
			v[dd]=g[i]*i;
			w[dd]=g[i];
		}
	}
	for(int i=1;i<=n;++i)B[i]=1e18;
	B[0]=0;
	for(int i=1;i<=dd;++i){
		for(int j=n;j>=v[i];--j){
			B[j]=min(B[j],w[i]+B[j-v[i]]);
		}
	}
	for(int i=1;i<=n;++i){
		if(B[i]==1e18)puts("-1");
		else printf("%lld\n",B[i]-1);
	}
	return 0;
}
0