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

• 問題: No.3506 All Distance is Square Number
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 09:34:25
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,677 bytes
• コンパイル時間: 3,345 ms
• コンパイル使用メモリ: 365,332 KB
• 実行使用メモリ: 9,856 KB
• 最終ジャッジ日時: 2026-04-18 09:35:11
• 合計ジャッジ時間: 9,458 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

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

ソースコード

#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 Candidate {
    vector<pair<int,int>> edges;
    vector<int> weights;
};

struct Solver {
    int N;
    mt19937_64 rng;
    chrono::steady_clock::time_point t0;

    explicit Solver(int n): N(n), rng((uint64_t)chrono::high_resolution_clock::now().time_since_epoch().count()) {
        t0 = chrono::steady_clock::now();
    }

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

    bool verify_and_collect(const Candidate& c, vector<vector<vector<int>>>& paths) {
        int M = (int)c.edges.size();
        if ((int)c.weights.size() != M) return false;
        if (M > 2 * N - 3) return false;

        vector<int> used(201, 0);
        for (int w : c.weights) {
            if (w < 1 || w > 200 || used[w]) return false;
            used[w] = 1;
        }

        vector<vector<pair<int,int>>> adj(N + 1);
        for (int i = 0; i < M; ++i) {
            auto [u, v] = c.edges[i];
            if (u < 1 || u > N || v < 1 || v > N || u == v) return false;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        // connectivity
        vector<int> vis_conn(N + 1, 0);
        deque<int> dq;
        dq.push_back(1);
        vis_conn[1] = 1;
        while (!dq.empty()) {
            int u = dq.front(); dq.pop_front();
            for (auto [v, _] : adj[u]) if (!vis_conn[v]) vis_conn[v] = 1, dq.push_back(v);
        }
        for (int v = 1; v <= N; ++v) if (!vis_conn[v]) return false;

        function<bool(int,int,int,vector<int>&,vector<int>&,vector<int>&)> dfs =
            [&](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(v, t, sum + c.weights[eid], vis, cur, out)) return true;
                    cur.pop_back();
                    vis[v] = 0;
                }
                return false;
            };

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

    bool verify_prefix(const Candidate& c, int V) {
        int M = (int)c.edges.size();
        if ((int)c.weights.size() != M) return false;
        vector<vector<pair<int,int>>> adj(V + 1);
        for (int i = 0; i < M; ++i) {
            auto [u, v] = c.edges[i];
            if (u < 1 || u > V || v < 1 || v > V || u == v) return false;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        vector<int> vis_conn(V + 1, 0);
        deque<int> dq;
        dq.push_back(1);
        vis_conn[1] = 1;
        while (!dq.empty()) {
            int u = dq.front(); dq.pop_front();
            for (auto [v, _] : adj[u]) if (!vis_conn[v]) vis_conn[v] = 1, dq.push_back(v);
        }
        for (int v = 1; v <= V; ++v) if (!vis_conn[v]) return false;

        function<bool(int,int,int,vector<int>&)> dfs = [&](int u, int t, int sum, vector<int>& vis) {
            if (u == t) return is_square(sum);
            for (auto [v, eid] : adj[u]) {
                if (vis[v]) continue;
                vis[v] = 1;
                if (dfs(v, t, sum + c.weights[eid], vis)) return true;
                vis[v] = 0;
            }
            return false;
        };

        for (int i = 1; i <= V; ++i) {
            for (int j = i + 1; j <= V; ++j) {
                vector<int> vis(V + 1, 0);
                vis[i] = 1;
                if (!dfs(i, j, 0, vis)) return false;
            }
        }
        return true;
    }

    bool try_fan(Candidate& out, double lim_sec) {
        if (N == 2) {
            out.edges = {{1, 2}};
            out.weights = {16};
            return true;
        }
        if (N == 3) {
            out.edges = {{1,2},{2,3},{1,3}};
            out.weights = {16,9,25};
            return true;
        }

        vector<pair<int,int>> edges;
        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});

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

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

        vector<vector<int>> seeds;
        if (N >= 5) {
            vector<int> s(N - 2, -1);
            s[0] = 8;
            s[1] = 38;
            s[2] = 158;
            seeds.push_back(s);
        }
        {
            vector<int> s(N - 2, -1);
            if (N - 2 >= 1) s[0] = 24;
            if (N - 2 >= 2) s[1] = 120;
            seeds.push_back(s);
        }
        seeds.push_back(vector<int>(N - 2, -1));

        vector<vector<vector<int>>> dummy;
        int tries = 0;
        while (!time_up(lim_sec)) {
            ++tries;
            Candidate cand;
            cand.edges = edges;
            cand.weights = base;

            vector<int> available = pool;
            shuffle(available.begin(), available.end(), rng);

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

            bool bad = 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 = true; break; }
                star[i] = seed[i];
                used[seed[i]] = 1;
            }
            if (bad) 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 = true; break; }
                star[i] = available[ptr++];
                used[star[i]] = 1;
            }
            if (bad) continue;
            for (int x : star) cand.weights.push_back(x);

            if (verify_and_collect(cand, dummy)) {
                out = cand;
                return true;
            }
        }
        return false;
    }

    bool try_incremental(Candidate& out, double lim_sec) {
        if (N <= 3) return try_fan(out, lim_sec);

        Candidate cur;
        cur.edges = {{1,2},{2,3},{1,3}};
        cur.weights = {16,9,25};
        vector<int> used(201, 0);
        used[16] = used[9] = used[25] = 1;

        auto check_to_new = [&](int v)->bool {
            return verify_prefix(cur, v);
        };

        for (int v = 4; v <= N; ++v) {
            if (time_up(lim_sec)) return false;
            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);

            bool ok = false;
            int tries = (v <= 10 ? 5000 : (v <= 30 ? 2500 : 1200));
            for (int t = 0; t < tries; ++t) {
                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];

                cur.edges.push_back({v, a});
                cur.weights.push_back(w1);
                cur.edges.push_back({v, b});
                cur.weights.push_back(w2);
                used[w1] = used[w2] = 1;

                if (check_to_new(v)) {
                    ok = true;
                    break;
                }

                used[w1] = used[w2] = 0;
                cur.edges.pop_back(); cur.weights.pop_back();
                cur.edges.pop_back(); cur.weights.pop_back();
                if (time_up(lim_sec)) break;
            }
            if (!ok) return false;
        }

        out = cur;
        return true;
    }

    bool construct(Candidate& out, vector<vector<vector<int>>>& paths) {
        // Strategy 1: fan-based random search (worked best in prior runs).
        if (try_fan(out, 8.5) && verify_and_collect(out, paths)) return true;
        // Strategy 2: incremental random attach fallback.
        if (try_incremental(out, 14.0) && verify_and_collect(out, 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);
    Candidate ans;
    vector<vector<vector<int>>> paths;

    if (!solver.construct(ans, paths)) {
        // Deterministic format-preserving fallback (may be WA).
        int M = max(1, N - 1);
        cout << M << '\n';
        if (N >= 2) {
            for (int i = 1; i <= N - 1; ++i) cout << i << ' ' << i + 1 << ' ' << (2 * i - 1) << '\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 << ans.edges.size() << '\n';
    for (int i = 0; i < (int)ans.edges.size(); ++i) {
        auto [u, v] = ans.edges[i];
        cout << u << ' ' << v << ' ' << ans.weights[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;
}