結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-01-19 12:29:42 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,272 bytes |
コンパイル時間 | 1,400 ms |
コンパイル使用メモリ | 156,704 KB |
実行使用メモリ | 17,792 KB |
最終ジャッジ日時 | 2025-01-19 12:31:24 |
合計ジャッジ時間 | 100,728 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 TLE * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long #define il inline #define N 2000005 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 * 10], v[N * 10], 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; for (int j = 1; t[i] >= j; j <<= 1) t[i] -= j, w[++cnt] = j * i, v[cnt] = j; w[++cnt] = i * t[i], v[cnt] = 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; }