結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2026-02-03 10:47:22
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,096 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 685 ms
コンパイル使用メモリ 70,508 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-02-03 10:47:30
合計ジャッジ時間 7,332 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 1 RE * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

// ????????????N??????1e4+10?
const int MAXN = 10000 + 10;
// ?????????????????N????????1?
const int INF = 0x3f3f3f3f;
// ???????????????
int parent[MAXN];
int sz[MAXN];
// DP???dp[x] = ????x???????????
int dp[MAXN];
// ?????????????????
vector<int> components;

// ?????????+???????????
inline int find(int u) {
    int root = u;
    while (parent[root] != root) root = parent[root];
    while (parent[u] != root) {
        int tmp = parent[u];
        parent[u] = root;
        u = tmp;
    }
    return root;
}

// ????????????
inline void unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
}

// ?????????????
inline int read() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x;
}

int main() {
    int N = read(), M = read();
    // ??????
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }
    // ??M??
    for (int i = 0; i < M; ++i) {
        int u = read(), v = read();
        unite(u, v);
    }
    // ?????????????????????
    vector<bool> vis(N + 1, false);
    for (int i = 1; i <= N; ++i) {
        int root = find(i);
        if (!vis[root]) {
            vis[root] = true;
            components.push_back(sz[root]);
        }
    }
    // ???DP???01???
    memset(dp, INF, sizeof(dp));
    for (int s : components) {
        dp[s] = 1; // ?????t=1
    }
    // 01?????????DP
    for (int s : components) {
        for (int x = N; x >= s; --x) {
            if (dp[x - s] != INF) {
                dp[x] = min(dp[x], dp[x - s] + 1);
            }
        }
    }
    // ??1~N???????????
    for (int i = 1; i <= N; ++i) {
        if (dp[i] == INF) {
            printf("-1 ");
        } else {
            printf("%d ", dp[i] - 1); // ????? = t-1
        }
    }
    printf("\n");
    return 0;
}
0