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

• 問題: No.3506 All Distance is Square Number
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 09:46:56
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 6,293 bytes
• コンパイル時間: 4,709 ms
• コンパイル使用メモリ: 362,516 KB
• 実行使用メモリ: 13,092 KB
• 最終ジャッジ日時: 2026-04-18 09:48:04
• 合計ジャッジ時間: 17,879 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

ファイルパターン	結果
other	AC * 20 WA * 1 TLE * 4 -- * 4

ソースコード

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

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

struct Edge { int u, v, w; };

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

    explicit Solver(int n): N(n) {}

    void build_fan() {
        edges.clear();
        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});
        adj.assign(N + 1, {});
        for (int i = 0; i < (int)edges.size(); ++i) {
            auto [u, v] = edges[i];
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }
    }

    bool dfs_find(int u, int t, int sum, vector<int>& vis, vector<int>& cur, vector<int>& out) {
        if (u == t) {
            if (is_square(sum)) {
                out = cur;
                return true;
            }
            return false;
        }
        if ((int)cur.size() >= N) return false;
        for (auto [v, eid] : adj[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            cur.push_back(eid);
            if (dfs_find(v, t, sum + weights[eid], vis, cur, out)) return true;
            cur.pop_back();
            vis[v] = 0;
        }
        return false;
    }

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

        paths.assign(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(i, j, 0, vis, cur, out)) return false;
                paths[i][j] = out;
            }
        }
        return true;
    }

    bool construct(vector<vector<vector<int>>>& paths) {
        if (N == 2) {
            build_fan();
            edges = {{1,2}};
            adj.assign(3, {});
            adj[1].push_back({2,0});
            adj[2].push_back({1,0});
            weights = {1};
            return verify_and_collect(paths);
        }
        if (N == 3) {
            edges = {{1,2},{2,3},{1,3}};
            adj.assign(4, {});
            for (int i=0;i<3;i++){
                auto [u,v]=edges[i];
                adj[u].push_back({v,i});
                adj[v].push_back({u,i});
            }
            weights = {16,9,25};
            return verify_and_collect(paths);
        }

        build_fan();
        int M = (int)edges.size();

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

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

        vector<vector<int>> seeds;
        if (N >= 5) {
            vector<int> s1;
            for (int k = 3; k <= N; ++k) {
                if (k == 3) s1.push_back(8);
                else if (k == 4) s1.push_back(38);
                else if (k == 5) s1.push_back(158);
                else s1.push_back(-1);
            }
            seeds.push_back(s1);
        }
        {
            vector<int> s2(N - 2, -1);
            if (N - 2 >= 1) s2[0] = 24;
            if (N - 2 >= 2) s2[1] = 120;
            seeds.push_back(s2);
        }
        seeds.push_back(vector<int>(N - 2, -1));

        mt19937_64 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());
        const int tries = 250000;

        for (int t = 0; t < tries; ++t) {
            weights = base;
            vector<int> available = pool;
            shuffle(available.begin(), available.end(), rng);

            auto seed = seeds[t % seeds.size()];
            vector<int> star(N - 2, -1);
            vector<int> used(201, 0);
            for (int x : base) used[x] = 1;

            bool bad_seed = false;
            for (int i = 0; i < N - 2; ++i) {
                if (seed[i] == -1) continue;
                if (seed[i] < 1 || seed[i] > 200 || used[seed[i]]) {
                    bad_seed = true;
                    break;
                }
                star[i] = seed[i];
                used[seed[i]] = 1;
            }
            if (bad_seed) continue;

            int ptr = 0;
            for (int i = 0; i < N - 2; ++i) {
                if (star[i] != -1) continue;
                while (ptr < (int)available.size() && used[available[ptr]]) ++ptr;
                if (ptr == (int)available.size()) { bad_seed = true; break; }
                star[i] = available[ptr++];
                used[star[i]] = 1;
            }
            if (bad_seed) continue;

            for (int x : star) weights.push_back(x);

            if (verify_and_collect(paths)) return true;
        }
        return false;
    }
};

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

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

    Solver solver(N);
    vector<vector<vector<int>>> paths;
    if (!solver.construct(paths)) {
        int M = N - 1;
        cout << M << '\n';
        for (int i = 1; i <= N - 1; ++i) {
            cout << i << ' ' << (i + 1) << ' ' << (2 * i - 1) << '\n';
        }
        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                cout << (j - i);
                for (int e = i; e <= j - 1; ++e) cout << ' ' << e;
                cout << '\n';
            }
        }
        return 0;
    }

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