結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2025-01-19 12:18:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,111 bytes
コンパイル時間 1,972 ms
コンパイル使用メモリ 198,420 KB
実行使用メモリ 20,236 KB
最終ジャッジ日時 2025-01-19 12:18:36
合計ジャッジ時間 26,751 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other WA * 32 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57){
		if(ch==45)f=-1;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
const int N=1e5+3;
int n,m;
vector<int> e[N];
int cur[N],s[N],cnt,v[N],cnt_[N];
int ans[N];
inline void dfs(int u,int fa){
	cur[u]=cnt;
	++s[cnt];
	for(int v:e[u]){
		if(v==fa||cur[v])continue;
		dfs(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(time(0));cin.tie(0),cout.tie(0);
	n=read(),m=read();
	for(int i=1,x,y;i<=m;++i){
		x=read(),y=read();
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}
	for(int i=1;i<=n;++i)if(!cur[i]){++cnt;dfs(i,0);}
//	cout<<1;
	for(int i=1;i<=n;++i)ans[i]=1e9;
	
	
	
	for(int i=1;i<=cnt;++i)ans[s[i]]=0,++cnt_[s[i]],v[i]=1;//cout<<i<<": "<<s[i]<<endl;
	
//	sort(s+1,s+1+cnt);
	
	for(int i=1;i<=cnt;++i){
		for(int j=n;j>=s[i];--j){
			if(j-s[i]==s[i]&&cnt_[s[i]]<=1)continue;
			ans[j]=min(ans[j],ans[j-s[i]]+v[i]);
		}
	}
	
	
	
	
	for(int i=1;i<=n;++i){
		if(ans[i]==1000000000)puts("-1");
		else cout<<ans[i]<<endl;
	}
	
	
	

	return 0;
}
0