結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー marc2825
提出日時 2026-05-25 09:14:58
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,651 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,270 ms
コンパイル使用メモリ 221,936 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-10 20:51:26
合計ジャッジ時間 5,523 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 1 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<pair<int, int>> edges;
    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            edges.push_back({u, v});
        }
    }

    int T = (int)edges.size();
    int E = T - M; // number of edges to keep

    // Too large for bit exhaustive search.
    if (T >= 63) {
        cout << "Too many edges for bit exhaustive search\n";
        return 0;
    }

    unsigned long long total = 1ULL << T;

    for (unsigned long long mask = 0; mask < total; ++mask) {
        if (__builtin_popcountll(mask) != E) continue;

        vector<vector<int>> G(N + 1);

        for (int i = 0; i < T; ++i) {
            if ((mask >> i) & 1ULL) {
                auto [u, v] = edges[i];
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }

        vector<int> dist(N + 1, -1);
        queue<int> q;

        dist[1] = 0;
        q.push(1);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int to : G[v]) {
                if (dist[to] != -1) continue;
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }

        if (dist[N] == K) {
            cout << "Yes\n";

            // Output removed edges.
            for (int i = 0; i < T; ++i) {
                if (((mask >> i) & 1ULL) == 0) {
                    auto [u, v] = edges[i];
                    cout << u << ' ' << v << '\n';
                }
            }

            return 0;
        }
    }

    cout << "No\n";
    return 0;
}
0