#1159250 (C++23) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 07:31:27
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 2,616 bytes
• コンパイル時間: 5,258 ms
• コンパイル使用メモリ: 351,300 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-18 07:31:40
• 合計ジャッジ時間: 7,460 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 1 WA * 28

ソースコード

#include <bits/stdc++.h>
using namespace std;
bool is_sq(int x) {
    if (x < 0) return false;
    int r = (int)std::sqrt(x);
    while (r * r < x) ++r;
    while (r * r > x) --r;
    return r * r == x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<array<int,3>> edges;
    auto add_edge = [&](int u, int v, int w) {
        edges.push_back({u, v, w});
        return (int)edges.size();
    };
    vector<bool> used(201, false);
    auto use = [&](int w) {
        used[w] = true;
    };
    int e_12 = add_edge(1, 2, 1);
    use(1);
    vector<int> e1(N+1, -1), e2(N+1, -1);
    vector<int> w1(N+1, -1), w2(N+1, -1);
    int cur = 2;
    for (int i = 3; i <= N; ++i) {
        while (cur <= 200 && used[cur]) ++cur;
        int a = cur++;
        while (cur <= 200 && used[cur]) ++cur;
        int b = cur++;
        w1[i] = a; w2[i] = b;
        e1[i] = add_edge(1, i, a);
        e2[i] = add_edge(2, i, b);
        use(a); use(b);
    }
    int M = edges.size();
    if (M > 2*N - 3) {
        cerr << "Edge limit exceeded\n";
        return 1;
    }
    vector<vector<vector<int>>> path_id(N+1, vector<vector<int>>(N+1));
    auto set_path = [&](int i, int j, const vector<int>& ids) {
        path_id[i][j] = ids;
    };
    set_path(1, 2, {e_12});
    for (int i = 3; i <= N; ++i) {
        set_path(1, i, {e1[i]});
        set_path(2, i, {e2[i]});
    }
    for (int i = 3; i <= N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            int a = w1[i], b = w2[i];
            int c = w1[j], d = w2[j];
            int e = 1;
            vector<pair<int, vector<int>>> cand;
            cand.push_back({a + c, {e1[i], e1[j]}});
            cand.push_back({b + d, {e2[i], e2[j]}});
            cand.push_back({a + e + d, {e1[i], e_12, e2[j]}});
            cand.push_back({b + e + c, {e2[i], e_12, e1[j]}});
            bool ok = false;
            for (auto& [sum, ids] : cand) {
                if (is_sq(sum)) {
                    set_path(i, j, ids);
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                set_path(i, j, cand[0].second);
            }
        }
    }
    cout << M << "\n";
    for (auto& [u, v, w] : edges) {
        cout << u << " " << v << " " << w << "\n";
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            cout << path_id[i][j].size();
            for (int id : path_id[i][j]) {
                cout << " " << id;
            }
            cout << "\n";
        }
    }
    return 0;
}