結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー marc2825
提出日時 2026-05-25 09:48:06
言語 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  
実行時間 -
コード長 2,958 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,420 ms
コンパイル使用メモリ 227,608 KB
実行使用メモリ 9,396 KB
最終ジャッジ日時 2026-07-10 20:52:31
合計ジャッジ時間 3,823 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 25 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int N, M, K;
vector<vector<bool>> removed;
vector<pair<int, int>> ans;

void print_no() {
    cout << "No\n";
}

void print_yes() {
    cout << "Yes\n";
    for (auto [u, v] : ans) {
        cout << u << ' ' << v << '\n';
    }
}

// BFSして、距離と親を返す
pair<int, vector<int>> bfs() {
    vector<int> dist(N + 1, -1);
    vector<int> par(N + 1, -1);
    queue<int> q;

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

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

        for (int to = 1; to <= N; ++to) {
            if (to == v) continue;

            int a = min(v, to);
            int b = max(v, to);
            if (removed[a][b]) continue;

            if (dist[to] == -1) {
                dist[to] = dist[v] + 1;
                par[to] = v;
                q.push(to);
            }
        }
    }

    return {dist[N], par};
}

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

    int T = N * (N - 1) / 2;

    removed.assign(N + 1, vector<bool>(N + 1, false));

    // WRONG GREEDY:
    // 現在の最短距離が K 未満なら、
    // その最短路上の最後の辺を消して距離を伸ばそうとする。
    while ((int)ans.size() < M) {
        auto [d, par] = bfs();

        if (d == -1) {
            // もう非連結になってしまった
            print_no();
            return 0;
        }

        if (d < K) {
            // 最短路を復元
            vector<int> path;
            int cur = N;
            while (cur != -1) {
                path.push_back(cur);
                cur = par[cur];
            }
            reverse(path.begin(), path.end());

            // WRONG:
            // 最短路の最後の辺を消せば距離が伸びるだろう、という雑な貪欲
            int u = path[(int)path.size() - 2];
            int v = path[(int)path.size() - 1];
            if (u > v) swap(u, v);

            if (removed[u][v]) {
                print_no();
                return 0;
            }

            removed[u][v] = true;
            ans.push_back({u, v});
        }
        else {
            // dist >= K になったら、あとは適当な辺を消す。
            // WRONG:
            // dist == K を維持できるか確認していない。
            bool erased = false;

            for (int u = 1; u <= N && !erased; ++u) {
                for (int v = u + 1; v <= N && !erased; ++v) {
                    if (removed[u][v]) continue;

                    removed[u][v] = true;
                    ans.push_back({u, v});
                    erased = true;
                }
            }

            if (!erased) break;
        }
    }

    // 最後に一応 BFS して、距離が K なら出す
    // ここを消すとさらに雑な嘘解法になる。
    auto [d, par] = bfs();

    if ((int)ans.size() == M && d == K) {
        print_yes();
    } else {
        print_no();
    }

    return 0;
}
0