結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-01-19 14:31:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,159 bytes |
コンパイル時間 | 1,437 ms |
コンパイル使用メモリ | 160,476 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2025-01-19 14:31:52 |
合計ジャッジ時間 | 5,409 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:25:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d%d",&n,&m); | ~~~~~^~~~~~~~~~~~~~ main.cpp:27:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | int u,v;scanf("%d%d",&u,&v); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,m; int head[N],nxt[N],ver[N],tot; int siz[N],dcc,vis[N],cnt[N]; int w[N],v[N],p,f[N]; void add(int u,int v){ ver[++tot]=v; nxt[tot]=head[u]; head[u]=tot; } void dfs(int u){ siz[dcc]++,vis[u]=1; for(int i=head[u];i;i=nxt[i]){ int v=ver[i]; if(!vis[v]) dfs(v); } } void Add(int s,int n){ for(int i=1;i<=n;i*=2) w[++p]=i*s,v[p]=i,n-=i; if(n) w[++p]=n*s,v[p]=n; } int main(){ scanf("%d%d",&n,&m); while(m--){ int u,v;scanf("%d%d",&u,&v); add(u,v),add(v,u); } for(int i=1;i<=n;i++){ if(!vis[i]) ++dcc,dfs(i); } //for(int i=1;i<=dcc;i++) cout<<siz[i]<<" ";cout<<endl; for(int i=1;i<=dcc;i++) cnt[siz[i]]++; for(int i=1;i<=n;i++) Add(i,cnt[i]); memset(f,63,sizeof(f)),f[0]=0; for(int i=1;i<=p;i++){ for(int j=n;j>=w[i];j--) f[j]=min(f[j],f[j-w[i]]+v[i]); } for(int i=1;i<=n;i++) printf("%d\n",(f[i]==f[N-1]?-1:f[i]-1)); return 0; }