結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2025-01-19 11:20:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,316 bytes
コンパイル時間 3,606 ms
コンパイル使用メモリ 193,168 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2025-01-19 11:22:23
合計ジャッジ時間 103,202 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 3 TLE * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
il ll rd(){
	ll s = 0, w = 1;
	char ch = getchar();
	for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
	for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
	return s * w;
}
ll n = rd(), m = rd(), fa[N], sz[N], w[N], v[N], cnt, t[N], f[N * 10];
il ll find(ll x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
const ll inf = 1e18;
int main(){
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) fa[find(rd())] = find(rd());
	for (int i = 1; i <= n; i++) sz[find(i)]++;
	for (int i = 1; i <= n; i++) if (fa[i] == i) t[sz[i]]++;
	for (int i = 1; i <= n; i++){
//		cout << t[i] << "A\n";
//		for (int j = 0; j <= 30; j++) if ((1 << j) <= t[i]) w[++cnt] = (1 << j) * i, v[cnt] = (1 << j);
//		for (int j = 1; j <= t[i]; j++) w[++cnt] = i, v[cnt] = 1;
		ll p = i, h = 1;
		for (int c = 1; t[i] >= c; c <<= 1){
		    t[i] -= c, w[++cnt] = c * p, v[cnt] = c * h;
		    c *= 2;
		  }
		  w[++cnt] = p * t[i], v[cnt]= h * t[i];
	}
	for (int i = 1; i <= n; i++) f[i] = inf;
	for (int i = 1; i <= cnt; i++)
		for (int j = n; j >= w[i]; j--)
			f[j] = min(f[j], f[j - w[i]] + v[i]);
	for (int i = 1; i <= n; i++) printf ("%lld\n", f[i] % inf - 1);
	return 0;
}
0