結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-01-19 12:39:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 988 bytes |
コンパイル時間 | 1,476 ms |
コンパイル使用メモリ | 164,888 KB |
実行使用メモリ | 8,004 KB |
最終ジャッジ日時 | 2025-01-19 12:39:41 |
合計ジャッジ時間 | 4,799 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:17:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | scanf("%d%d",&n,&m); | ~~~~~^~~~~~~~~~~~~~ main.cpp:22:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 22 | scanf("%d%d",&u,&v); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> #define ll long long using namespace std; int n,m; vector<int> g[100010]; int fa[100010]; int siz[100010]; int tot=0,a[100010],t[100010]; int dp[100010]; inline int find(int k) { if(k==fa[k]) return k; return fa[k]=find(fa[k]); } int main() { scanf("%d%d",&n,&m); for(register int i=1;i<=n;i++) fa[i]=i,siz[i]=1; for(register int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); int fx=find(u),fy=find(v); if(fx==fy) continue; fa[fx]=fy,siz[fy]+=siz[fx],siz[fx]=0; } for(register int i=1;i<=n;i++) if(fa[i]==i) tot++,a[tot]=siz[i],t[a[tot]]++; sort(a+1,a+tot+1); tot=unique(a+1,a+tot+1)-a-1; dp[0]=0; for(register int i=1;i<=n;i++) dp[i]=1e9; for(register int i=1;i<=tot;i++) for(register int k=1;t[a[i]]>0;k*=2) { int x=min(k,t[a[i]]); for(register int j=n;j>=a[i]*x;j--) dp[j]=min(dp[j],dp[j-a[i]*x]+x); t[a[i]]-=x; } for(register int i=1;i<=n;i++) if(dp[i]==1e9) puts("-1"); else printf("%d\n",dp[i]-1); return 0; }