結果

問題 No.317 辺の追加
ユーザー tails
提出日時 2015-12-10 23:48:35
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 441 ms
コード長 874 Byte
コンパイル時間 1,086 ms
使用メモリ 17,264 KB
最終ジャッジ日時 2019-05-16 03:55:31

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 5 ms
3,060 KB
sample2.txt AC 5 ms
3,056 KB
subtask1_01.txt AC 243 ms
10,192 KB
subtask1_02.txt AC 294 ms
13,116 KB
subtask1_03.txt AC 202 ms
7,644 KB
subtask1_04.txt AC 306 ms
13,992 KB
subtask1_05.txt AC 383 ms
16,016 KB
subtask1_06.txt AC 106 ms
7,228 KB
subtask1_07.txt AC 221 ms
7,056 KB
subtask1_08.txt AC 305 ms
11,756 KB
subtask1_09.txt AC 441 ms
16,920 KB
subtask1_10.txt AC 143 ms
4,144 KB
subtask1_11.txt AC 431 ms
16,964 KB
subtask1_12.txt AC 161 ms
4,884 KB
subtask1_13.txt AC 347 ms
13,696 KB
subtask1_14.txt AC 410 ms
15,932 KB
subtask1_15.txt AC 252 ms
8,856 KB
subtask1_16.txt AC 371 ms
14,492 KB
subtask1_17.txt AC 432 ms
16,816 KB
subtask1_18.txt AC 439 ms
17,264 KB
subtask1_19.txt AC 231 ms
8,016 KB
subtask2_01.txt AC 116 ms
7,196 KB
subtask2_02.txt AC 62 ms
5,176 KB
subtask2_03.txt AC 65 ms
5,312 KB
subtask2_04.txt AC 197 ms
10,280 KB
subtask2_05.txt AC 136 ms
8,900 KB
subtask2_06.txt AC 146 ms
8,864 KB
subtask2_07.txt AC 119 ms
7,768 KB
subtask2_08.txt AC 64 ms
5,248 KB
subtask2_09.txt AC 19 ms
3,652 KB
subtask2_10.txt AC 230 ms
9,780 KB
subtask2_11.txt AC 229 ms
9,784 KB
subtask2_12.txt AC 226 ms
9,784 KB
subtask2_13.txt AC 225 ms
9,784 KB
subtask2_14.txt AC 229 ms
9,788 KB
subtask2_15.txt AC 228 ms
9,784 KB
subtask2_16.txt AC 231 ms
9,788 KB
subtask2_17.txt AC 227 ms
9,784 KB
subtask2_18.txt AC 233 ms
9,780 KB
subtask2_19.txt AC 234 ms
9,788 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

#define Nmax 100010
bool used[Nmax];
list<int> edges[Nmax];
int cs[Nmax];
int dp[Nmax];

int countf(int i){
	if(used[i]) return 0;
	used[i]=true;
	int result = 1;
	for(auto it=edges[i].begin(); it!=edges[i].end(); ++it){
		result += countf(*it);
	}
	return result;
}

int main(){
	int N,M;
	cin>>N>>M;

	for(int j=0;j<M;++j){
		int u,v;
		cin>>u>>v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	
	dp[0]=-1;
	for(int k=1;k<=N;++k){
		dp[k]=N;
	}

	for(int i=1;i<=N;++i){
		int c = countf(i);
		++cs[c];
	}

	int sum=0;
	for(int c=1;c<=N;++c){
		int s=cs[c];
		int d=1;
		while(s){
			int e=d;
			if(e>s)e=s;
			s-=e;
			int ce=c*e;
			sum+=ce;
			for(int k=sum-ce;k>=0;--k){
				if(dp[k+ce]>e+dp[k]){
					dp[k+ce]=e+dp[k];
				}
			}
			d*=2;
		}
	}

	for(int k=1;k<=N;++k){
		cout << (dp[k]<N?dp[k]:-1) << endl;
	}
}
0