結果

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

ソースコード

diff #
raw source code 

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

// ??N?1e5????????????2e5+10?
const int MAXN = 1e5 + 10;
// ???????????????1e5??????
const int INF = 0x3f3f3f3f;
// ???????????????
int parent[MAXN];
int sz[MAXN];
// DP???dp[x] = ????x??????????
int dp[MAXN];
// ??????1<<20=1MB?????1e5???
char buf[1 << 20];
int buf_pos;

// ???????getchar?????????????
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;
}

// ?????????????????-1?????
inline void write(int x) {
    if (x < 0) { // ??-1
        buf[buf_pos++] = '-';
        buf[buf_pos++] = '1';
        buf[buf_pos++] = '\n';
        return;
    }
    // ?????????
    int tmp[10], cnt = 0;
    if (x == 0) tmp[cnt++] = 0;
    while (x) {
        tmp[cnt++] = x % 10;
        x /= 10;
    }
    // ???????????
    while (cnt--) buf[buf_pos++] = tmp[cnt] + '0';
    buf[buf_pos++] = '\n';
}

// ?????????+???????????
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];
}

int main() {
    // ????????
    buf_pos = 0;
    // ??N?M
    int N = read(), M = read();
    
    // ???????1~N?????????
    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);
    vector<int> components;
    for (int i = 1; i <= N; ++i) {
        int root = find(i);
        if (!vis[root]) {
            vis[root] = true;
            components.push_back(sz[root]);
        }
    }
    
    // ???DP???????????
    memset(dp, 0x3f, sizeof(dp));
    for (int s : components) {
        if (s <= N) dp[s] = 1; // ?????????1?
    }
    
    // ??????01????????????????
    for (int s : components) {
        // ??????01???????0/1????1??cnt=1?
        int cnt = 1, w = s, val = 1;
        // ???????????????
        for (int x = N; x >= w; --x) {
            if (dp[x - w] != INF) {
                dp[x] = min(dp[x], dp[x - w] + val);
            }
        }
    }
    
    // ??1~N????????????N?????????
    for (int i = 1; i <= N; ++i) {
        if (dp[i] == INF) write(-1);
        else write(dp[i] - 1); // ????? = ???-1
    }
    
    // ??????????????
    fwrite(buf, 1, buf_pos, stdout);
    fflush(stdout);
    
    return 0;
}
0