#1166628 (C++17) No.3585 Make Ends Meet (Easy)

• 問題: No.3585 Make Ends Meet (Easy)
• ユーザー: marc2825
• 提出日時: 2026-05-25 09:46:59
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 3,430 bytes
• コンパイル時間: 1,330 ms
• コンパイル使用メモリ: 225,152 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-10 20:52:30
• 合計ジャッジ時間: 3,574 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	WA * 2
other	AC * 9 WA * 39

ソースコード

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

int N, M, K;
vector<vector<bool>> keep;

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

void print_yes() {
    cout << "Yes\n";
    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            if (!keep[u][v]) {
                cout << u << ' ' << v << '\n';
            }
        }
    }
}

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

    int T = N * (N - 1) / 2;
    int E = T - M; // number of edges to keep

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

    // Very rough feasibility check.
    if (E <= 0) {
        print_no();
        return 0;
    }

    // WRONG IDEA:
    // Split vertices 2..N-1 into about (K-1)/2 layers,
    // then make each layer a clique.
    int L = max(1, (K - 1) / 2);

    vector<vector<int>> layer(L);
    for (int v = 2; v <= N - 1; ++v) {
        int id = (v - 2) % L;
        layer[id].push_back(v);
    }

    // Connect 1 to the first layer.
    for (int v : layer[0]) {
        keep[1][v] = true;
    }

    // Connect N to the last layer.
    for (int v : layer[L - 1]) {
        int a = min(v, N);
        int b = max(v, N);
        keep[a][b] = true;
    }

    // Make each layer a complete graph.
    // This is suspicious because edges inside a layer do not necessarily help create distance K,
    // and may create many unintended short paths.
    for (int i = 0; i < L; ++i) {
        for (int a = 0; a < (int)layer[i].size(); ++a) {
            for (int b = a + 1; b < (int)layer[i].size(); ++b) {
                int u = layer[i][a];
                int v = layer[i][b];
                if (u > v) swap(u, v);
                keep[u][v] = true;
            }
        }
    }

    // Connect consecutive layers completely.
    // This also does not correspond to the correct shortest-distance construction.
    for (int i = 0; i + 1 < L; ++i) {
        for (int u : layer[i]) {
            for (int v : layer[i + 1]) {
                if (u > v) swap(u, v);
                keep[u][v] = true;
            }
        }
    }

    // If K is odd/even, try to adjust by adding direct-ish edges.
    // This is arbitrary and wrong.
    if (K % 2 == 0 && L > 0) {
        for (int v : layer[0]) {
            int u = min(1, v);
            int w = max(1, v);
            keep[u][w] = true;
        }
    }

    // Count kept edges.
    vector<pair<int, int>> kept_edges;
    vector<pair<int, int>> not_kept_edges;

    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            if (keep[u][v]) kept_edges.push_back({u, v});
            else not_kept_edges.push_back({u, v});
        }
    }

    // If too many edges are kept, remove arbitrary kept edges.
    // This may destroy the intended connection.
    while ((int)kept_edges.size() > E) {
        auto [u, v] = kept_edges.back();
        kept_edges.pop_back();
        keep[u][v] = false;
    }

    // If too few edges are kept, add arbitrary missing edges.
    // This may create a shortcut and make the shortest distance smaller than K.
    int ptr = 0;
    while ((int)kept_edges.size() < E && ptr < (int)not_kept_edges.size()) {
        auto [u, v] = not_kept_edges[ptr++];
        keep[u][v] = true;
        kept_edges.push_back({u, v});
    }

    if ((int)kept_edges.size() != E) {
        print_no();
        return 0;
    }

    // WRONG:
    // Does not verify that dist(1,N) is exactly K.
    print_yes();
    return 0;
}