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

• 問題: No.3506 All Distance is Square Number
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 09:21:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,948 bytes
• コンパイル時間: 3,549 ms
• コンパイル使用メモリ: 363,468 KB
• 実行使用メモリ: 11,940 KB
• 最終ジャッジ日時: 2026-04-18 09:22:00
• 合計ジャッジ時間: 8,682 ms
• ジャッジサーバーID （参考情報）: judge2_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; // (to, eid)
    array<int, 201> used{};
    mt19937_64 rng;
    chrono::steady_clock::time_point t0;
    double time_limit_sec = 8.0;

    explicit Constructor(int n, uint64_t seed): N(n), rng(seed) {
        t0 = chrono::steady_clock::now();
    }

    bool time_up() const {
        double dt = chrono::duration<double>(chrono::steady_clock::now() - t0).count();
        return dt > time_limit_sec;
    }

    void reset_base() {
        edges.clear();
        used.fill(0);
        adj.assign(max(4, N + 1), {});

        if (N >= 2) {
            edges.push_back({1, 2, 16});
            used[16] = 1;
            adj[1].push_back({2, 0});
            adj[2].push_back({1, 0});
        }
        if (N >= 3) {
            edges.push_back({2, 3, 9});
            edges.push_back({1, 3, 25});
            used[9] = used[25] = 1;
            adj[2].push_back({3, 1});
            adj[3].push_back({2, 1});
            adj[1].push_back({3, 2});
            adj[3].push_back({1, 2});
        }
    }

    bool dfs_find(int s, int t, vector<int>& out_path) {
        vector<int> vis(N + 1, 0), path;
        vis[s] = 1;
        bool found = false;

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

        go(s, 0);
        return found;
    }

    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;
    }

    struct Choice { int a, b, w1, w2; };

    vector<Choice> collect_choices_for_vertex(int v, int target_choices) {
        vector<Choice> out;
        unordered_set<unsigned long long> seen;

        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 trials = (v <= 10 ? 12000 : (v <= 25 ? 5000 : (v <= 50 ? 2200 : 900)));
        uniform_int_distribution<int> dv(0, (int)verts.size() - 1);
        uniform_int_distribution<int> dw(0, (int)free_w.size() - 1);

        for (int it = 0; it < trials && (int)out.size() < target_choices; ++it) {
            if (time_up()) break;
            int a = verts[dv(rng)], b = verts[dv(rng)];
            if (a == b) continue;
            if (a > b) swap(a, b);
            int i1 = dw(rng), i2 = dw(rng);
            if (i1 == i2) continue;
            int w1 = free_w[i1], w2 = free_w[i2];

            unsigned long long key = (unsigned long long)a;
            key = key * 131ULL + (unsigned long long)b;
            key = key * 257ULL + (unsigned long long)min(w1, w2);
            key = key * 257ULL + (unsigned long long)max(w1, w2);
            if (seen.count(key)) continue;
            seen.insert(key);

            add_edge(v, a, w1);
            add_edge(v, b, w2);
            if (check_pairs_with_new_vertex(v)) {
                out.push_back({a, b, w1, w2});
            }
            pop_last_edge();
            pop_last_edge();
        }

        return out;
    }

    bool build_rec(int v) {
        if (time_up()) return false;
        if (v > N) return true;

        int need = (v <= 12 ? 5 : (v <= 25 ? 3 : 1));
        auto choices = collect_choices_for_vertex(v, need);
        if (choices.empty()) return false;

        shuffle(choices.begin(), choices.end(), rng);
        for (auto &c : choices) {
            add_edge(v, c.a, c.w1);
            add_edge(v, c.b, c.w2);
            if (build_rec(v + 1)) return true;
            pop_last_edge();
            pop_last_edge();
        }
        return false;
    }

    bool build() {
        if (N == 1) return false;
        if (N == 2) {
            reset_base();
            edges.resize(1);
            return true;
        }
        reset_base();
        if (N == 3) return true;

        const int restarts = 20;
        for (int rep = 0; rep < restarts; ++rep) {
            if (time_up()) break;
            reset_base();
            if (build_rec(4)) 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)) {
        // Deterministic fallback to keep output format parseable.
        int M = max(1, N - 1);
        cout << M << '\n';
        if (N >= 2) {
            for (int i = 1; i < N; ++i) cout << i << ' ' << i + 1 << ' ' << i << '\n';
        } else {
            cout << "1 1 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 << (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;
}