結果
問題 | No.317 辺の追加 |
ユーザー |
![]() |
提出日時 | 2018-11-07 16:25:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 317 ms / 2,000 ms |
コード長 | 1,604 bytes |
コンパイル時間 | 1,962 ms |
コンパイル使用メモリ | 203,104 KB |
最終ジャッジ日時 | 2025-01-06 15:48:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}struct UnionFind{int n;vector<int> r,p;UnionFind(){}UnionFind(int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}int find(int x){return (x==p[x]?x:p[x]=find(p[x]));}bool same(int x,int y){return find(x)==find(y);}void unite(int x,int y){x=find(x);y=find(y);if(x==y) return;if(r[x]<r[y]) swap(x,y);r[x]+=r[y];p[y]=x;}};//INSERT ABOVE HEREsigned main(){int n,m;cin>>n>>m;UnionFind uf(n);for(int i=0;i<m;i++){int x,y;cin>>x>>y;x--;y--;uf.unite(x,y);}vector<int> v;for(int i=0;i<n;i++)if(uf.find(i)==i) v.emplace_back(uf.r[i]);const int BS = 400;vector<int> cnt(BS,0);using P = pair<int, int>;vector<P> vs;for(int x:v){if(x<BS) cnt[x]++;else vs.emplace_back(x,1);}for(int t=1;t<BS;t++){if(!cnt[t]) continue;for(int k=1;k<=cnt[t];k<<=1){vs.emplace_back(t*k,k);cnt[t]-=k;}if(cnt[t]) vs.emplace_back(t*cnt[t],cnt[t]);}const int INF = 1e9;vector<int> dp(n+1,INF);dp[0]=0;for(P p:vs){int d=p.first,c=p.second;vector<int> nx(n+1,INF);for(int i=0;i<=n;i++){chmin(nx[i],dp[i]);if(i+d<=n) chmin(nx[i+d],dp[i]+c);}swap(dp,nx);}for(int i=1;i<=n;i++){if(dp[i]==INF) dp[i]=0;cout<<dp[i]-1<<endl;}return 0;}