結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>

using namespace std;

long long n,m,vis[100005],Pow[30],cnt,Size,A[100005],w[100005],num[100005],k,f[100005],B[100005];
vector<int>e[100005];
void dfs(int x) {
	vis[x]=1,Size++;
	for(auto v:e[x]) if(!vis[v]) dfs(v);
}
int main() {
	cin>>n>>m,Pow[0]=1;
	for(int i=1;i<=25;i++) Pow[i]=Pow[i-1]*2;
	for(int i=1;i<=m;i++) {
		int x,y;
		cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
	} 
	for(int i=1;i<=n;i++) if(!vis[i]) Size=0,dfs(i),A[++cnt]=Size;
	sort(A+1,A+cnt+1);
	for(int i=1;i<=cnt;i++) if(A[i]!=A[i-1]) w[++k]=A[i],num[k]=1;
	else num[k]++;
	memset(A,0,sizeof A),cnt=0;
	for(int i=1;i<=k;i++) {
		for(int j=0;j<=25;j++) if(num[i]>=Pow[j]) num[i]-=Pow[j],A[++cnt]=w[i]*Pow[j],B[cnt]=Pow[j];
		if(num[i]) A[++cnt]=w[i]*num[i],B[cnt]=num[i];
	}
	memset(f,0x3f,sizeof f),f[0]=0;
	for(int i=1;i<=cnt;i++) for(int j=n;j>=A[i];j--) f[j]=min(f[j],f[j-A[i]]+B[i]);
	for(int i=1;i<=n;i++) if(f[i]==0x3f3f3f3f3f3f3f3f) cout<<"-1\n";
	else cout<<f[i]-1<<"\n";
	return 0;
}
0