結果
問題 | No.317 辺の追加 |
ユーザー |
![]() |
提出日時 | 2015-12-10 01:08:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,209 bytes |
コンパイル時間 | 1,386 ms |
コンパイル使用メモリ | 168,180 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 07:02:55 |
合計ジャッジ時間 | 8,374 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
// Template {{{#include <bits/stdc++.h>#define REP(i,n) for(int i=0; i<(int)(n); ++i)using namespace std;typedef long long LL;#ifdef LOCAL#include "contest.h"#else#define dump(x)#endifconst int dx[4] = {1, 0, -1, 0};const int dy[4] = {0, 1, 0, -1};inline bool valid(int x, int w) { return 0 <= x && x < w; }void iostream_init() {ios::sync_with_stdio(false);cin.tie(0);cout.setf(ios::fixed);cout.precision(12);}//}}}struct UnionFind {vector<int> data;UnionFind(int N) : data(N, -1) { }// xとyを併合するbool unite(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[x] > data[y]) swap(x, y);data[x] += data[y]; data[y] = x;}return x != y;}// xとyが同じ集合にあるか判定するbool same(int x, int y) {return root(x) == root(y);}// xを含む集合の要素数を求めるint size(int x) {return -data[root(x)];}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}};int main(){iostream_init();int N, M;while(cin >> N >> M) {UnionFind uf(N);REP(i, M) {int a, b;cin >> a >> b;a--; b--;uf.unite(a, b);}map<int, int> counter;REP(i, N) if(uf.root(i) == i) {int size = uf.size(i);counter[size] ++;}const int INF = 1e9;vector<int> min_cost(N + 1, INF);min_cost[0] = 0;for(const auto& p : counter) {int size = p.first;int count = p.second;for(int k = 0; count > 0; k++) {int use = min(count, 1 << k);int value = size * use;int cost = 1 * use;for(int i = N - value; i >= 0; i--) {min_cost[i + value] = min(min_cost[i + value], min_cost[i] + cost);}count -= use;}}REP(i, N) {int ans = min_cost[i+1];cout << (ans == INF ? -1 : ans-1) << endl;}}return 0;}