結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 11:40:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 1,174 bytes
コンパイル時間 1,874 ms
コンパイル使用メモリ 194,264 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-19 11:40:29
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0; char ch; bool f=0;
    while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
    if(ch=='-') f=1;
    else x=ch^48;
    while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
    return f?-x:x;
}
const int N=1e5+5,B=333;
int n,fa[N],sz[N];
int get(int x){
    return x==fa[x]?x:fa[x]=get(fa[x]);
}
int c[N],f[N];
int main(){
    n=read(); int m=read();
    for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    while(m--){
        int x=read(),y=read();
        x=get(x),y=get(y);
        if(x==y) continue;
        if(sz[x]>sz[y]) swap(x,y);
        sz[y]+=sz[x],fa[x]=y;
    }
    for(int i=1;i<=n;i++) f[i]=1e9;
    for(int i=1;i<=n;i++){
        if(get(i)==i) c[sz[i]]++;
    }
    f[0]=0;
    for(int i=1;i<=n;i++){
        if(i>B){
            while(c[i]--){
                for(int j=n;j>=i;j--) f[j]=min(f[j],f[j-i]+1); 
            }
        }
        else{
            for(int j=1;c[i]>=j;j=j*2){
                c[i]-=j;
                for(int t=n;t>=j*i;t--) f[t]=min(f[t],f[t-j*i]+j);
            }
            if(c[i]){
                for(int t=n;t>=c[i]*i;t--) f[t]=min(f[t],f[t-c[i]*i]+c[i]);
            }
        }
//      cerr<<i<<": ";
//      for(int j=1;j<=n;j++) cout<<f[j]<<" "; puts("");
    }
    for(int i=1;i<=n;i++){
        if(f[i]<=n) printf("%d\n",f[i]-1);
        else puts("-1");
    }
    return 0;
} 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0