結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
const int MAXN =1e5+5;

using namespace std;
vector<int> e[MAXN];
unordered_map<int,int> rcd;
int fa[MAXN],dp[MAXN],num[MAXN],cnt[MAXN];
int n,m,tot;

int find( int x) {
	return x==fa[x] ? x:fa[x] =find(fa[x]);
}

int main() {
	ios::sync_with_stdio(false);
	
	cin >>n >>m;
	for ( int i=1; i<=n; i++) fa[i] =i;
	for ( int i=1; i<=m; i++) {
		int u,v; cin >>u >>v;
		if ( u==v) continue;
		if ( u>v) swap(u,v);
		e[u].push_back(v),e[v].push_back(u);
		int fu =find(u),fv =find(v);
//		cout <<fu <<' '<<fv <<"\n \n";
		fa[fv] =fu;
	}
	
	for ( int i=1; i<=n; i++) ++num[find(i)];
	for ( int i=1; i<=n; i++) 
		if ( num[i]) ++cnt[num[i]];
	
	int sum =0;
	memset(dp,0x3f,sizeof(dp));
	dp[0] =-1;
	for ( int i=1; i<=n; i++) {
		int s =cnt[i],d =1;
		while ( s) {
			int tmp =d,x;
			if ( tmp >s) tmp =s;
			x =i*tmp,s -=tmp;
			sum +=x;
			for ( int j=sum-x; ~j; j--) 
				dp[j+x] =min(dp[j+x],tmp+dp[j]);
			d <<=1;
		}
	}
	for ( int i=1; i<=n; i++) 
		cout <<(dp[i]<n? dp[i] : -1) <<'\n';
	
	return 0;
}
/****
6 3
2 3
4 5
5 6
****/
0