結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 12:40:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 1,322 bytes
コンパイル時間 1,931 ms
コンパイル使用メモリ 195,588 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2025-01-19 12:40:23
合計ジャッジ時間 5,000 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void wt(long long int)’:
main.cpp:20:29: warning: ‘t’ may be used uninitialized [-Wmaybe-uninitialized]
   20 |                 int st[10], t;
      |                             ^

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
ll n, m, fa[N], sz[N], w[N], v[N], cnt, t[N], f[N];
il ll find(ll x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
const ll inf = 1e18;
void wt(ll x){
    if (x == -1) putchar('-'), putchar('1');
    else if (x == 0) putchar('0');
    else{
        int st[10], t;
        while (x) st[++t] = x % 10, x /= 10;
        while (t) putchar(st[t] + '0'), t--;
    }
    putchar('\n');
}
int main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) fa[find(rd())] = find(rd());
    for (int i = 1; i <= n; i++) sz[find(i)]++;
    for (int i = 1; i <= n; i++) if (fa[i] == i) t[sz[i]]++;
    for (int i = 1; i <= n; i++){
//      cout << t[i] << "A\n";
        for (int j = 1; t[i] >= j; j <<= 1) t[i] -= j, w[++cnt] = j * i, v[cnt] = j;
        if (t[i]) w[++cnt] = i * t[i], v[cnt] = t[i];
    }
    for (int i = 1; i <= n; i++) f[i] = inf;
    for (int i = 1; i <= cnt; 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++) wt((f[i] == inf ? 0 : f[i]) - 1);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0