結果

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

ソースコード

diff #
raw source code 

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

int N, M, K;

int calc_dist(const vector<pair<int, int>>& removed_edges) {
    vector<vector<bool>> removed(N + 1, vector<bool>(N + 1, false));

    for (auto [u, v] : removed_edges) {
        if (u > v) swap(u, v);
        removed[u][v] = true;
    }

    vector<vector<int>> G(N + 1);
    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            if (removed[u][v]) continue;
            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);
        }
    }

    return dist[N];
}

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

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

    vector<vector<bool>> is_path_edge(N + 1, vector<bool>(N + 1, false));

    // Fix the path 1 - 2 - ... - K - N.
    for (int i = 1; i < K; ++i) {
        is_path_edge[i][i + 1] = true;
    }
    is_path_edge[K][N] = true;

    vector<pair<int, int>> candidates;

    // Only non-path edges are candidates for deletion.
    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            if (is_path_edge[u][v]) continue;
            candidates.push_back({u, v});
        }
    }

    // If even all non-path edges are not enough, output No.
    if ((int)candidates.size() < M) {
        cout << "No\n";
        return 0;
    }

    mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());

    const double TIME_LIMIT = 1.8;
    auto start = chrono::steady_clock::now();

    while (true) {
        auto now = chrono::steady_clock::now();
        double elapsed = chrono::duration<double>(now - start).count();

        if (elapsed > TIME_LIMIT) {
            cout << "No\n";
            return 0;
        }

        shuffle(candidates.begin(), candidates.end(), rng);

        vector<pair<int, int>> removed_edges;
        for (int i = 0; i < M; ++i) {
            removed_edges.push_back(candidates[i]);
        }

        if (calc_dist(removed_edges) == K) {
            cout << "Yes\n";
            for (auto [u, v] : removed_edges) {
                cout << u << ' ' << v << '\n';
            }
            return 0;
        }
    }
}
0