結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 12:42:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 1,050 bytes
コンパイル時間 1,607 ms
コンパイル使用メモリ 166,540 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2025-01-19 12:43:00
合計ジャッジ時間 5,216 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
const int MAXN =1e5+5;
using namespace std;
vector<int> e[MAXN];
unordered_map<int,int> rcd;
int fa[MAXN],dp[MAXN],num[MAXN],cnt[MAXN];
int n,m,tot;
int find( int x) {
    return x==fa[x] ? x:fa[x] =find(fa[x]);
}
int main() {
    ios::sync_with_stdio(false);
    
    cin >>n >>m;
    for ( int i=1; i<=n; i++) fa[i] =i;
    for ( int i=1; i<=m; i++) {
        int u,v; cin >>u >>v;
        if ( u==v) continue;
        if ( u>v) swap(u,v);
        e[u].push_back(v),e[v].push_back(u);
        int fu =find(u),fv =find(v);
//      cout <<fu <<' '<<fv <<"\n \n";
        fa[fv] =fu;
    }
    
    for ( int i=1; i<=n; i++) ++num[find(i)];
    for ( int i=1; i<=n; i++) 
        if ( num[i]) ++cnt[num[i]];
    
    int sum =0;
    memset(dp,0x3f,sizeof(dp));
    dp[0] =-1;
    for ( int i=1; i<=n; i++) {
        int s =cnt[i],d =1;
        while ( s) {
            int tmp =d,x;
            if ( tmp >s) tmp =s;
            x =i*tmp,s -=tmp;
            sum +=x;
            for ( int j=sum-x; ~j; j--) 
                dp[j+x] =min(dp[j+x],tmp+dp[j]);
            d <<=1;
        }
    }
    for ( int i=1; i<=n; i++) 
        cout <<(dp[i]<n? dp[i] : -1) <<'\n';
    
    return 0;
}
/****
6 3
2 3
4 5
5 6
****/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0