結果
問題 | No.317 辺の追加 |
ユーザー |
![]() |
提出日時 | 2015-12-12 15:58:19 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 247 ms / 2,000 ms |
コード長 | 1,496 bytes |
コンパイル時間 | 841 ms |
コンパイル使用メモリ | 86,012 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-09-15 08:44:32 |
合計ジャッジ時間 | 9,728 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <iostream>#include <stdio.h>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <stack>#include <algorithm>#include <functional>#include <cmath>#include <string>using namespace std;typedef vector <int> VI;typedef vector <VI> VVI;typedef vector <string> VS;typedef pair<int,int> PII;typedef long long LL;typedef vector <LL> VLL;typedef unsigned long long ULL;typedef pair <int, LL> PIL;typedef vector <PIL> VPIL;//#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)//#define sort(c) sort((c).begin(),(c).end())#define range(i,a,b) for(int i=(a); i < (b); i++)#define rep(i,n) range(i,0,n)int parent[100001];int root(int x){if (x != parent[x]) parent[x] = root(parent[x]);return parent[x];}int main(){int N,M,u,v,w,num,mul;map <int,int> conn_comp, comp_num;map <int,int> :: iterator mit;VI ans;cin >> N >> M;ans = VI(N+1,N); ans[0] = 0;rep(i,N) parent[i] = i;rep(i,M){cin >> u >> v;u = root(u-1); v = root(v-1);if (u!=v) parent[u] = v;}rep(i,N) conn_comp[root(i)]++;for (mit=conn_comp.begin();mit!=conn_comp.end();mit++) comp_num[mit->second]++;for (mit=comp_num.begin();mit!=comp_num.end();mit++){num = mit->second;for (int i = 1; num > 0; i<<=1){mul = min(i,num);w = mul*mit->first;for (int j = N; j >= w; j--) ans[j] = min(ans[j],ans[j-w]+mul);num -= mul;}}rep(i,N) cout << (ans[i+1]==N ? -1 : ans[i+1]-1) << endl;return 0;}