結果

問題 No.317 辺の追加
ユーザー catuppercatupper
提出日時 2015-12-09 23:58:28
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 813 bytes
コンパイル時間 550 ms
コンパイル使用メモリ 60,000 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-15 06:04:42
合計ジャッジ時間 7,956 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,752 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 633 ms
5,376 KB
testcase_03 AC 217 ms
5,376 KB
testcase_04 AC 1,972 ms
5,376 KB
testcase_05 AC 149 ms
5,376 KB
testcase_06 AC 205 ms
5,376 KB
testcase_07 AC 63 ms
5,376 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

#define INF (1 << 29)

int dp[108000], dd[108000];
int mm, n, m, x, y;
int cnt[108000], res[108000];
int u[108000];

int r(int x){
	if(u[x] == x)return x;
	return u[x] = r(u[x]);
}

void unite(int x, int y){
//	if(r(x) == r(y))return;
	x = r(x);
	y = r(y);
	u[x] = y;
}

int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++)u[i] = i;
	for(int i = 0;i < m;i++){
		cin >> x >> y;
		unite(x, y);
	}
	for(int i = 1;i <= n;i++){
		cnt[r(i)]++;
	}
	fill(dp, dp + n + 3, INF);
	dp[0] = 0;
	for(int i = 1;i <= n;i++){
		if(cnt[i]){
			for(int j = n;j - cnt[i] >= 0;j--){
				dp[j] = min(dp[j], dp[j - cnt[i]] + 1);
			}
		}
	}
	for(int i = 1;i <= n;i++){
		if(dp[i] == INF)cout << -1 << endl;
		else cout << dp[i] - 1 << endl;
	}
	return 0;	
}
0