結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-01-19 16:42:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,493 bytes |
コンパイル時間 | 1,791 ms |
コンパイル使用メモリ | 195,224 KB |
実行使用メモリ | 10,336 KB |
最終ジャッジ日時 | 2025-01-19 16:43:05 |
合計ジャッジ時間 | 5,028 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 13 WA * 25 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int fa[N]; int things[N]; int n,m; int find(int x){ if(x==fa[x])return x; else{ fa[x]=find(fa[x]); return fa[x]; } } void marge(int x,int y){ x=find(x),y=find(y); fa[x]=y; } struct node{ int to,nxt; }a[N<<2]; int head[N],tot; void add(int u,int v){ a[++tot].to=v; a[tot].nxt=head[u]; head[u]=tot; } int js=0; bool book[N]; void dfs(int now){ //cout<<now<<" "; for(int i=head[now];i!=0;i=a[i].nxt){ if(book[a[i].to])continue; book[a[i].to]=1; js++; dfs(a[i].to); } return; } struct object{ int num,val; }t[N]; int cnt,cnt2=0; int v[N],w[N]; int dp[N]; void work(){ memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=cnt;i++){ int s=t[i].num,x=t[i].val; int k=1; while(k<=s){ v[++cnt2]=k*x; w[cnt2]=k-1; s-=k; k*=2; } if(s){ v[++cnt2]=x*s; w[cnt2]=s-1; } } dp[0]=0; for(int i=1;i<=cnt2;i++){ for(int j=n;j>=v[i];j--){ dp[j]=min(dp[j],dp[j-v[i]]+w[i]+1); } } } int main(){ std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; marge(u,v); add(u,v); add(v,u); } cnt=0; for(int i=1;i<=n;i++){ if(fa[i]==i){ js=0,dfs(i); cnt++; things[js]++; } } cnt=0; for(int i=1;i<=n;i++){ if(things[i]){ t[++cnt].num=things[i]; t[cnt].val=i; } } work(); for(int i=1;i<=n;i++){ if(dp[i]<N)cout<<dp[i]-1<<"\n"; else cout<<-1<<"\n"; } return 0; }