結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2025-01-19 12:12:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 373 ms / 2,000 ms |
コード長 | 1,459 bytes |
コンパイル時間 | 2,130 ms |
コンパイル使用メモリ | 163,172 KB |
実行使用メモリ | 6,144 KB |
最終ジャッジ日時 | 2025-01-19 12:12:59 |
合計ジャッジ時間 | 10,482 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:13:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 13 | scanf("%d%d",&n,&m); | ~~~~~^~~~~~~~~~~~~~ main.cpp:17:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | scanf("%d%d",&u,&v); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; int n, m; int fa[200002], siz[200002]; inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);} int fac[200002], tot; int cnt[200002], ql, qr, f[2][200002]; pair<int,int> q[200002]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i] = i, siz[i] = 1; for(int i=1;i<=m;i++){ int u, v, fu, fv; scanf("%d%d",&u,&v); fu = getfa(u), fv = getfa(v); if(fu == fv) continue; fa[fu] = fv, siz[fv] += siz[fu]; } for(int i=1;i<=n;i++) { if(fa[i] == i) fac[++tot] = siz[i]; } for(int i=1;i<=n;i++) cnt[fac[i]]++; //f[i][j] = min(f[i-1][k]+(j-k)/ii) for(int j=1;j<=n;j++) f[0][j] = 1e9; f[0][0] = -1; for(int ii=1;ii<=n;ii++){ if(cnt[ii] == 0) continue; for(int jl=0;jl<ii;jl++){ ql = 1, qr = 0; for(int j=jl,k=0;j<=n;j+=ii,k++){ if(j != jl){ while(ql <= qr && q[qr].second >= f[0][j-ii]-k+1) qr--; q[++qr] = make_pair(k-1, f[0][j-ii]-k+1); } while(ql <= qr && k-q[ql].first > cnt[ii]) ql++; /*if(ii == 2 && jl == 0) { cout << endl; for(int i=ql;i<=qr;i++) cout << q[i].first << ' ' << q[i].second << endl; }*/ if(j == jl) f[1][j] = f[0][j]; else f[1][j] = min(f[0][j], q[ql].second+k); } } //cout << endl; for(int j=0;j<=n;j++) f[0][j] = f[1][j], f[1][j] = 0/*, cout << f[0][j] << ' ' << endl*/; } for(int i=1;i<=n;i++) { if(f[0][i] == 1e9) cout << -1 << endl; else cout << f[0][i] << endl; } return 0; }