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

• 問題: No.3506 All Distance is Square Number
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 08:57:41
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,163 bytes
• コンパイル時間: 2,989 ms
• コンパイル使用メモリ: 364,092 KB
• 実行使用メモリ: 11,428 KB
• 最終ジャッジ日時: 2026-04-18 08:58:12
• 合計ジャッジ時間: 7,234 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 13 TLE * 1 -- * 15

ソースコード

#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 Constructor {
    int N;
    vector<Edge> edges;
    vector<vector<pair<int,int>>> adj;
    array<int, 201> used{};
    mt19937_64 rng;

    explicit Constructor(int n, uint64_t seed): N(n), rng(seed) {}

    void reset_base() {
        edges.clear();
        used.fill(0);
        int base_w[3] = {16, 9, 25};
        pair<int,int> base_e[3] = {{1,2}, {2,3}, {1,3}};
        for (int i = 0; i < 3; ++i) {
            edges.push_back({base_e[i].first, base_e[i].second, base_w[i]});
            used[base_w[i]] = 1;
        }
        int curN = min(3, N);
        adj.assign(curN + 1, {});
        for (int i = 0; i < (int)edges.size(); ++i) {
            auto &e = edges[i];
            adj[e.u].push_back({e.v, i});
            adj[e.v].push_back({e.u, i});
        }
    }

    bool dfs_find(int s, int t, vector<int>& out_path) {
        int curN = (int)adj.size() - 1;
        vector<int> vis(curN + 1, 0), path;
        vis[s] = 1;
        function<bool(int,int)> go = [&](int u, int sum) {
            if (u == t) {
                if (is_square(sum)) {
                    out_path = path;
                    return true;
                }
                return false;
            }
            for (auto [v, eid] : adj[u]) {
                if (vis[v]) continue;
                vis[v] = 1;
                path.push_back(eid);
                if (go(v, sum + edges[eid].w)) return true;
                path.pop_back();
                vis[v] = 0;
            }
            return false;
        };
        return go(s, 0);
    }

    bool check_pairs_with_new_vertex(int v) {
        vector<int> tmp;
        for (int i = 1; i < v; ++i) {
            if (!dfs_find(i, v, tmp)) return false;
        }
        return true;
    }

    void add_edge(int u, int v, int w) {
        int id = (int)edges.size();
        edges.push_back({u, v, w});
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
        used[w] = 1;
    }

    void pop_last_edge() {
        auto e = edges.back();
        edges.pop_back();
        adj[e.u].pop_back();
        adj[e.v].pop_back();
        used[e.w] = 0;
    }

    bool build() {
        if (N == 2) {
            edges = {{1, 2, 16}};
            adj.assign(3, {});
            adj[1].push_back({2, 0});
            adj[2].push_back({1, 0});
            return true;
        }
        if (N == 3) {
            reset_base();
            return true;
        }
        const int RESTART = 250;
        for (int rep = 0; rep < RESTART; ++rep) {
            reset_base();
            bool ok = true;

            for (int v = 4; v <= N; ++v) {
                adj.push_back({});
                vector<int> free_w;
                for (int x = 1; x <= 200; ++x) if (!used[x]) free_w.push_back(x);
                vector<int> verts(v - 1);
                iota(verts.begin(), verts.end(), 1);

                int tries;
                if (v <= 8) tries = 12000;
                else if (v <= 20) tries = 5000;
                else tries = 1800;

                bool found = false;
                for (int it = 0; it < tries; ++it) {
                    int a = verts[uniform_int_distribution<int>(0, (int)verts.size() - 1)(rng)];
                    int b = verts[uniform_int_distribution<int>(0, (int)verts.size() - 1)(rng)];
                    if (a == b) continue;

                    int i1 = uniform_int_distribution<int>(0, (int)free_w.size() - 1)(rng);
                    int i2 = uniform_int_distribution<int>(0, (int)free_w.size() - 1)(rng);
                    if (i1 == i2) continue;
                    int w1 = free_w[i1], w2 = free_w[i2];

                    add_edge(v, a, w1);
                    add_edge(v, b, w2);
                    if (check_pairs_with_new_vertex(v)) {
                        found = true;
                        break;
                    }
                    pop_last_edge();
                    pop_last_edge();
                }

                if (!found) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }

    bool collect_paths(vector<vector<vector<int>>>& paths) {
        paths.assign(N + 1, vector<vector<int>>(N + 1));
        for (int i = 1; i <= N; ++i) {
            for (int j = i + 1; j <= N; ++j) {
                if (!dfs_find(i, j, paths[i][j])) return false;
            }
        }
        return true;
    }
};

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

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

    uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
    Constructor ctor(N, seed);
    vector<vector<vector<int>>> paths;

    if (!ctor.build() || !ctor.collect_paths(paths)) {
        if (N == 2) {
            cout << 1 << '\n' << "1 2 16\n" << "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\n1 3\n1 2\n";
            return 0;
        }
        int M = 2 * N - 3;
        cout << M << '\n';
        int w = 1;
        for (int i = 1; i < N; ++i) cout << i << ' ' << i + 1 << ' ' << w++ << '\n';
        for (int i = 3; i <= N; ++i) cout << 1 << ' ' << i << ' ' << w++ << '\n';
        for (int i = 1; i <= N; ++i)
            for (int j = i + 1; j <= N; ++j)
                cout << "1 1\n";
        return 0;
    }

    cout << (int)ctor.edges.size() << '\n';
    for (auto &e : ctor.edges) cout << e.u << ' ' << e.v << ' ' << e.w << '\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;
}