結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2026-02-03 16:32:40
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,325 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 974 ms
コンパイル使用メモリ 92,324 KB
実行使用メモリ 30,108 KB
最終ジャッジ日時 2026-02-03 16:32:46
合計ジャッジ時間 5,758 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N=500005;
ll n,m;
ll hea[N],nex[N],rot[N],nod[N],idx,num[N],dp[N],dp2[N];
ll me[N];
void con(ll a,ll b){
	nex[idx]=hea[a];
	hea[a]=idx;
	nod[idx]=b;
}
ll root(ll poi){
	for(;rot[poi]!=rot[rot[poi]];){
		rot[poi]=rot[rot[poi]];
	}
	return rot[poi];
}
void prodp(ll w,ll c){
	if(dp[w]>-1){
		prodp(w*2,c+dp[w]);
		dp[w]=min(dp[w],c);
	}
	else{
		dp[w]=c;
	}
}
int main(){
	memset(dp,-1,sizeof(dp));
	memset(hea,-1,sizeof(hea));
	memset(nex,-1,sizeof(nex));
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		rot[i]=i;
		num[i]=1;
	}
	for(ll i=1;i<=m;i++){
		ll a,b;
		cin>>a>>b;
		if(a==b){
			continue;
		}
		con(a,b);
		con(b,a);
		if(root(a)<root(b)){
			rot[b]=rot[a];
			num[a]+=num[b];
			num[b]=0;
		}
		rot[a]=rot[b];
		num[b]+=num[a];
		num[a]=0;
	}
	for(ll i=1;i<=n;i++){
		me[num[i]]+=1;
	}
	//
	dp[0]=0;
	for(ll i=1;i<=n;i++){
		for(ll j=n;j>=0;j-=1){
			for(ll k=1;k<=me[i];k++){
				if((j-i*k)<0)break;
				if(dp[j-i*k]==-1)continue;
				if(dp[j]<=0)dp[j]=N*N;
				dp[j]=min(dp[j],dp[j-i*k]+k);
			}
		}
	}
//	for(ll i=1;i<=n;i++){
//		for(ll j=1;j<=me[i];j++){
//			prodp(j*i,j-1);
//		}
//	}
	for(ll i=1;i<=n;i++){
		if(i!=1){
			cout<<endl;
		}
		if(dp[i]==-1){
			cout<<-1;
			continue;
		}
		cout<<dp[i]-1;
	}
	
}
0