結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 12:18:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,111 bytes
コンパイル時間 1,972 ms
コンパイル使用メモリ 198,420 KB
実行使用メモリ 20,236 KB
最終ジャッジ日時 2025-01-19 12:18:36
合計ジャッジ時間 26,751 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other WA * 32 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57){
        if(ch==45)f=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
const int N=1e5+3;
int n,m;
vector<int> e[N];
int cur[N],s[N],cnt,v[N],cnt_[N];
int ans[N];
inline void dfs(int u,int fa){
    cur[u]=cnt;
    ++s[cnt];
    for(int v:e[u]){
        if(v==fa||cur[v])continue;
        dfs(v,u);
    }
}
signed main(){
    ios::sync_with_stdio(time(0));cin.tie(0),cout.tie(0);
    n=read(),m=read();
    for(int i=1,x,y;i<=m;++i){
        x=read(),y=read();
        e[x].emplace_back(y);
        e[y].emplace_back(x);
    }
    for(int i=1;i<=n;++i)if(!cur[i]){++cnt;dfs(i,0);}
//  cout<<1;
    for(int i=1;i<=n;++i)ans[i]=1e9;
    
    
    
    for(int i=1;i<=cnt;++i)ans[s[i]]=0,++cnt_[s[i]],v[i]=1;//cout<<i<<": "<<s[i]<<endl;
    
//  sort(s+1,s+1+cnt);
    
    for(int i=1;i<=cnt;++i){
        for(int j=n;j>=s[i];--j){
            if(j-s[i]==s[i]&&cnt_[s[i]]<=1)continue;
            ans[j]=min(ans[j],ans[j-s[i]]+v[i]);
        }
    }
    
    
    
    
    for(int i=1;i<=n;++i){
        if(ans[i]==1000000000)puts("-1");
        else cout<<ans[i]<<endl;
    }
    
    
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0