結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9;
int n,m;
int tot,vis[N],t[N];
int cnt,a[N],v[N],f[N];
vector<int>mp[N];
void dfs(int x)
{
	vis[x]=1,tot++;
	for(auto v:mp[x])
		if(!vis[v])dfs(v); 
}
int main()
{
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])tot=0,dfs(i),t[tot]++;
	for(int i=1;i<=n;i++)
	{
		if(t[i]==0)continue;
		for(int j=1;j<=t[i];j<<=1)
			t[i]-=j,cnt++,a[cnt]=j*i,v[cnt]=j;
		cnt++,a[cnt]=t[i]*i,v[cnt]=t[i];
	}
	for(int i=1;i<=n;i++)f[i]=INF;
	f[0]=0;
	for(int i=1;i<=cnt;i++)
		for(int j=n;j>=a[i];j--)
			if(f[j-a[i]]!=INF)
				f[j]=min(f[j],f[j-a[i]]+v[i]);
	for(int i=1;i<=n;i++)
		if(f[i]==INF)cout<<-1<<"\n";
		else cout<<f[i]-1<<"\n";
	return 0; 
}
0