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

• 問題: No.3506 All Distance is Square Number
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 09:05:15
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 10,526 bytes
• コンパイル時間: 3,578 ms
• コンパイル使用メモリ: 368,116 KB
• 実行使用メモリ: 16,192 KB
• 最終ジャッジ日時: 2026-04-18 09:06:19
• 合計ジャッジ時間: 15,408 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
other	AC * 6 WA * 4 TLE * 2 -- * 17

ソースコード

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

static inline bool is_square_int(int x) {
    if (x <= 0) return false;
    int r = (int)std::sqrt((double)x);
    while ((long long)r * r < x) ++r;
    while ((long long)r * r > x) --r;
    return (long long)r * r == x;
}

struct Solver {
    int N, M;
    vector<pair<int,int>> edges;
    vector<int> w;
    vector<vector<pair<int,int>>> adj;

    explicit Solver(int n): N(n) {
        for (int k = 1; k <= N - 1; ++k) edges.push_back({k, k + 1});
        for (int k = 3; k <= N; ++k) edges.push_back({1, k});
        M = (int)edges.size();

        adj.assign(N + 1, {});
        for (int i = 0; i < M; ++i) {
            auto [u, v] = edges[i];
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }
    }

    vector<vector<int>> candidates_for_pair(int i, int j) {
        vector<vector<int>> cands;

        auto add_spine = [&](int a, int b, vector<int>& seq) {
            if (a < b) {
                for (int x = a; x < b; ++x) seq.push_back(x - 1);
            } else if (a > b) {
                for (int x = a - 1; x >= b; --x) seq.push_back(x - 1);
            }
        };

        {
            vector<int> path;
            add_spine(i, j, path);
            cands.push_back(path);
        }

        vector<int> Ts;
        Ts.push_back(1);
        for (int t = 3; t <= i; ++t) Ts.push_back(t);

        vector<int> Ss;
        Ss.push_back(1);
        for (int s = 3; s <= j; ++s) Ss.push_back(s);

        for (int t : Ts) {
            for (int s : Ss) {
                vector<int> path;

                add_spine(i, t, path);

                if (t != 1) path.push_back((N - 1) + (t - 3));
                if (s != 1) path.push_back((N - 1) + (s - 3));

                add_spine(s, j, path);

                vector<int> usedV(N + 1, 0);
                int cur = i;
                usedV[cur] = 1;
                bool ok = true;
                for (int eid : path) {
                    auto [u, v] = edges[eid];
                    int nxt = -1;
                    if (u == cur) nxt = v;
                    else if (v == cur) nxt = u;
                    else { ok = false; break; }
                    if (usedV[nxt]) { ok = false; break; }
                    usedV[nxt] = 1;
                    cur = nxt;
                }
                if (ok && cur == j) cands.push_back(path);
            }
        }

        sort(cands.begin(), cands.end());
        cands.erase(unique(cands.begin(), cands.end()), cands.end());
        return cands;
    }

    bool verify_and_collect(const vector<vector<vector<vector<int>>>>& pair_cands,
                            vector<vector<vector<int>>>& ans_paths) {
        if ((int)w.size() != M) return false;
        vector<int> used(201, 0);
        for (int x : w) {
            if (x < 1 || x > 200 || used[x]) return false;
            used[x] = 1;
        }

        ans_paths.assign(N + 1, vector<vector<int>>(N + 1));
        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                bool ok = false;
                for (auto &p : pair_cands[i][j]) {
                    int sum = 0;
                    for (int eid : p) sum += w[eid];
                    if (is_square_int(sum)) {
                        ans_paths[i][j] = p;
                        ok = true;
                        break;
                    }
                }
                if (!ok) return false;
            }
        }
        return true;
    }

    int unsatisfied_count(const vector<vector<vector<vector<int>>>>& pair_cands) {
        int bad = 0;
        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                bool ok = false;
                for (auto &p : pair_cands[i][j]) {
                    int sum = 0;
                    for (int eid : p) sum += w[eid];
                    if (is_square_int(sum)) { ok = true; break; }
                }
                if (!ok) ++bad;
            }
        }
        return bad;
    }

    bool construct(vector<vector<vector<int>>>& paths) {
        vector<vector<vector<vector<int>>>> pair_cands(N + 1, vector<vector<vector<int>>>(N + 1));
        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                pair_cands[i][j] = candidates_for_pair(i, j);
            }
        }

        vector<int> spine;
        for (int k = 1; k <= N - 1; ++k) spine.push_back(2 * k - 1);

        vector<int> pool;
        vector<int> used(201, 0);
        for (int x : spine) used[x] = 1;
        for (int x = 1; x <= 200; ++x) if (!used[x]) pool.push_back(x);

        std::mt19937 rng((uint32_t)chrono::high_resolution_clock::now().time_since_epoch().count());

        int best_bad = INT_MAX;
        vector<int> best_w;

        const int restarts = 120;
        const int iters = 800;

        for (int r = 0; r < restarts; ++r) {
            vector<int> stars = pool;
            shuffle(stars.begin(), stars.end(), rng);
            stars.resize(max(0, N - 2));

            w = spine;
            for (int x : stars) w.push_back(x);

            int cur_bad = unsatisfied_count(pair_cands);
            if (cur_bad < best_bad) {
                best_bad = cur_bad;
                best_w = w;
            }
            if (cur_bad == 0 && verify_and_collect(pair_cands, paths)) return true;

            for (int it = 0; it < iters; ++it) {
                vector<int> cand_w = w;

                if (N - 2 >= 2 && (rng() & 1)) {
                    int a = (int)(rng() % (N - 2));
                    int b = (int)(rng() % (N - 2));
                    if (a != b) swap(cand_w[(N - 1) + a], cand_w[(N - 1) + b]);
                } else if (N - 2 >= 1) {
                    vector<int> used_now(201, 0);
                    for (int x : cand_w) used_now[x] = 1;
                    vector<int> unused;
                    for (int x : pool) if (!used_now[x]) unused.push_back(x);
                    if (!unused.empty()) {
                        int pos = (int)(rng() % (N - 2));
                        cand_w[(N - 1) + pos] = unused[rng() % unused.size()];
                    }
                }

                auto old_w = w;
                w.swap(cand_w);
                int nxt_bad = unsatisfied_count(pair_cands);

                if (nxt_bad < cur_bad || ((rng() % 1000) < 25)) {
                    cur_bad = nxt_bad;
                    if (cur_bad < best_bad) {
                        best_bad = cur_bad;
                        best_w = w;
                    }
                    if (cur_bad == 0 && verify_and_collect(pair_cands, paths)) return true;
                } else {
                    w.swap(old_w);
                }
            }
        }

        if (!best_w.empty()) w = best_w;
        return false;
    }
};

static bool dfs_find_path(int u, int t, const vector<vector<pair<int,int>>>& g, const vector<int>& w,
                          vector<int>& vis, vector<int>& cur, vector<int>& out, int sum) {
    if (u == t) {
        if (is_square_int(sum)) { out = cur; return true; }
        return false;
    }
    for (auto [v, eid] : g[u]) {
        if (vis[v]) continue;
        vis[v] = 1;
        cur.push_back(eid);
        if (dfs_find_path(v, t, g, w, vis, cur, out, sum + w[eid])) return true;
        cur.pop_back();
        vis[v] = 0;
    }
    return false;
}

static bool emit_small_fan_solution(int N) {
    vector<int> stars;
    if (N == 4) stars = {24, 120};
    else if (N == 5) stars = {8, 38, 158};
    else if (N == 6) stars = {24, 120, 35, 48};
    else if (N == 7) stars = {99, 138, 113, 101, 71};
    else return false;

    vector<pair<int,int>> edges;
    vector<int> w;
    for (int k = 1; k <= N - 1; ++k) {
        edges.push_back({k, k + 1});
        w.push_back(2 * k - 1);
    }
    for (int k = 3; k <= N; ++k) edges.push_back({1, k});
    for (int x : stars) w.push_back(x);

    int M = (int)edges.size();
    vector<vector<pair<int,int>>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        auto [u, v] = edges[i];
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }

    vector<vector<vector<int>>> paths(N + 1, vector<vector<int>>(N + 1));
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            vector<int> vis(N + 1, 0), cur, out;
            vis[i] = 1;
            if (!dfs_find_path(i, j, g, w, vis, cur, out, 0)) return false;
            paths[i][j] = out;
        }
    }

    cout << M << '\n';
    for (int i = 0; i < M; ++i) {
        auto [u, v] = edges[i];
        cout << u << ' ' << v << ' ' << w[i] << '\n';
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            cout << paths[i][j].size();
            for (int eid : paths[i][j]) cout << ' ' << (eid + 1);
            cout << '\n';
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    if (N == 2) {
        cout << 1 << '\n';
        cout << "1 2 1\n";
        cout << "1 1\n";
        return 0;
    }
    if (N == 3) {
        cout << 3 << '\n';
        cout << "1 2 16\n";
        cout << "2 3 9\n";
        cout << "1 3 25\n";
        cout << "1 1\n";
        cout << "1 3\n";
        cout << "1 2\n";
        return 0;
    }
    if (N <= 7 && emit_small_fan_solution(N)) return 0;

    Solver solver(N);
    vector<vector<vector<int>>> paths;

    bool ok = solver.construct(paths);
    if (!ok) {
        cout << solver.M << '\n';
        for (int i = 0; i < solver.M; ++i) {
            auto [u, v] = solver.edges[i];
            int ww = (i < (int)solver.w.size() ? solver.w[i] : i + 1);
            ww = max(1, min(200, ww));
            cout << u << ' ' << v << ' ' << ww << '\n';
        }
        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                cout << (j - i);
                for (int x = i; x < j; ++x) cout << ' ' << x;
                cout << '\n';
            }
        }
        return 0;
    }

    cout << solver.M << '\n';
    for (int i = 0; i < solver.M; ++i) {
        auto [u, v] = solver.edges[i];
        cout << u << ' ' << v << ' ' << solver.w[i] << '\n';
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            auto &p = paths[i][j];
            cout << p.size();
            for (int eid : p) cout << ' ' << (eid + 1);
            cout << '\n';
        }
    }

    return 0;
}