結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2026-02-03 18:23:07
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,041 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,218 ms
コンパイル使用メモリ 110,672 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-02-03 18:23:14
合計ジャッジ時間 5,513 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 4 WA * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:65:16: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   65 |     for (auto& [s, cnt] : block_cnt) {
      |                ^

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdio>
#include <algorithm>
using namespace std;

// ???????? + ?????
struct DSU {
    vector<int> parent;
    vector<long long> size; // ?????
    DSU(int n) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 1; i <= n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        // ??????????????
        if (size[x] < size[y]) swap(x, y);
        parent[y] = x;
        size[x] += size[y];
    }
};

int main() {
    // ??????????????
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    DSU dsu(N);

    // ??????????????????????
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        if (u == v) continue;
        dsu.unite(u, v);
    }

    // ???????????
    unordered_map<int, int> block_cnt;
    vector<bool> vis(N + 1, false);
    for (int i = 1; i <= N; ++i) {
        int root = dsu.find(i);
        if (!vis[root]) {
            vis[root] = true;
            block_cnt[dsu.size[root]]++;
        }
    }

    // ???DP???dp[j] = ????j???????
    const int INF = N + 10; // ??????N?????1???
    vector<int> dp(N + 1, INF);
    dp[0] = 0;

    // ?????????
    for (auto& [s, cnt] : block_cnt) {
        int remain = cnt;
        for (int k = 1; remain > 0; k <<= 1) {
            int take = min(k, remain);
            int vol = take * s;   // ?????
            int cost = take;      // ????????
            // 01??????
            for (int j = N; j >= vol; --j) {
                if (dp[j - vol] != INF && dp[j - vol] + cost < dp[j]) {
                    dp[j] = dp[j - vol] + cost;
                }
            }
            remain -= take;
        }
    }

    // ?????t????t-1??
    for (int i = 1; i <= N; ++i) {
        cout << dp[i] - 1 << '\n';
    }

    return 0;
}
0