結果
問題 | No.317 辺の追加 |
ユーザー |
![]() |
提出日時 | 2015-12-29 02:50:02 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 2,069 bytes |
コンパイル時間 | 834 ms |
コンパイル使用メモリ | 83,200 KB |
実行使用メモリ | 8,832 KB |
最終ジャッジ日時 | 2024-09-19 08:21:32 |
合計ジャッジ時間 | 5,755 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <algorithm>#include <map>#include <set>using namespace std;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define all(c) begin(c), end(c)using ll = long long;struct UnionFind {vector<int> par;int cnt;UnionFind(int size_) : par(size_, -1), cnt(size_) { }bool merge(int x, int y) {x = find(x); y = find(y);if (x != y) {if (par[y] < par[x]) swap(x, y);par[x] += par[y]; par[y] = x; cnt--;}return x != y;}bool get(int x, int y) { return find(x) == find(y); }int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }int size(int x) { return -par[find(x)]; }int size() { return cnt; }};int n, m;vector<int> u, v;void solve() {UnionFind uf(n);rep(i, m) {uf.merge(u[i] - 1, v[i] - 1);}set<int> vis; // root, sizemap<int, int> cnt;rep(i, n) {if (vis.count(uf.find(i))) continue;vis.insert(uf.find(i));cnt[uf.size(i)]++;}vector<int> size, cost;for (auto &p : cnt) {int i = 1;while (i <= p.second) {size.push_back(p.first*i);cost.push_back(i);p.second -= i;i *= 2;}i /= 2;if (p.second == 0) continue;size.push_back(p.first * p.second);cost.push_back(p.second);}static int dp[200010];fill(all(dp), 1000000000);dp[0] = 0;for (int i = 0; i < cost.size(); i++) {for (int j = n; j >= size[i]; --j) {if (j == size[i]) {dp[j] = min(dp[j], cost[i] - 1);}else {dp[j] = min(dp[j], dp[j - size[i]] + cost[i]);}}}for (int i = 0; i < n; i++) {cout << (dp[i + 1] == 1000000000 ? -1 : dp[i + 1]) << '\n';}}int main() {while (cin >> n >> m) {u.resize(m); v.resize(m);rep(i, m) cin >> u[i] >> v[i];solve();}}