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

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:28:27
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,209 bytes
• コンパイル時間: 1,862 ms
• コンパイル使用メモリ: 233,596 KB
• 実行使用メモリ: 9,984 KB
• 最終ジャッジ日時: 2026-04-18 06:28:56
• 合計ジャッジ時間: 7,031 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <random>
#include <algorithm>
using namespace std;
struct Edge {
    int to;
    int weight;
    int id;
};
int N;
vector<vector<Edge>> adj;
vector<int> path_res;
vector<int> current_path;
bool found_path;
int dfs_steps;
bool is_sq[40005];
bool vis[105];
void dfs(int u, int target, int sum) {
    if (found_path || dfs_steps > 250) return;
    dfs_steps++;
    if (u == target) {
        if (sum < 40005 && is_sq[sum]) {
            found_path = true;
            path_res = current_path;
        }
        return;
    }
    for (const auto& edge : adj[u]) {
        if (!vis[edge.to]) {
            vis[edge.to] = true;
            current_path.push_back(edge.id);
            dfs(edge.to, target, sum + edge.weight);
            if (found_path) return;
            current_path.pop_back();
            vis[edge.to] = false;
        }
    }
}
bool check_all_pairs() {
    for (int d = 1; d < N; ++d) {
        for (int i = 1; i <= N - d; ++i) {
            int j = i + d;
            found_path = false;
            dfs_steps = 0;
            current_path.clear();
            fill(vis, vis + N + 1, false);
            vis[i] = true;
            dfs(i, j, 0);
            if (!found_path) return false;
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N)) return 0;
    fill(is_sq, is_sq + 40005, false);
    for (int i = 1; i * i < 40005; ++i) {
        is_sq[i * i] = true;
    }
    vector<int> even_weights;
    for (int i = 2; i <= 200; i += 2) {
        even_weights.push_back(i);
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<pair<pair<int, int>, int>> edges_output;
    while (true) {
        shuffle(even_weights.begin(), even_weights.end(), rng);
        adj.assign(N + 1, vector<Edge>());
        edges_output.clear();
        int edge_count = 1;
        for (int i = 1; i < N; ++i) {
            int weight = 2 * i - 1;
            adj[i].push_back({i + 1, weight, edge_count});
            adj[i + 1].push_back({i, weight, edge_count});
            edges_output.push_back({{i, i + 1}, weight});
            edge_count++;
        }
        for (int i = 1; i <= N - 2; ++i) {
            int weight = even_weights[i - 1];
            adj[i].push_back({i + 2, weight, edge_count});
            adj[i + 2].push_back({i, weight, edge_count});
            edges_output.push_back({{i, i + 2}, weight});
            edge_count++;
        }
        if (check_all_pairs()) {
            break;
        }
    }
    cout << edges_output.size() << "\n";
    for (const auto& e : edges_output) {
        cout << e.first.first << " " << e.first.second << " " << e.second << "\n";
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            found_path = false;
            dfs_steps = 0;
            current_path.clear();
            fill(vis, vis + N + 1, false);
            vis[i] = true;
            auto dfs_output = [&](auto& self, int u, int target, int sum) -> void {
                if (found_path || dfs_steps > 10000) return;
                dfs_steps++;
                if (u == target) {
                    if (sum < 40005 && is_sq[sum]) {
                        found_path = true;
                        path_res = current_path;
                    }
                    return;
                }
                for (const auto& edge : adj[u]) {
                    if (!vis[edge.to]) {
                        vis[edge.to] = true;
                        current_path.push_back(edge.id);
                        self(self, edge.to, target, sum + edge.weight);
                        if (found_path) return;
                        current_path.pop_back();
                        vis[edge.to] = false;
                    }
                }
            };
            dfs_output(dfs_output, i, j, 0);
            cout << path_res.size() << "\n";
            for (int k = 0; k < path_res.size(); ++k) {
                cout << path_res[k] << (k == path_res.size() - 1 ? "" : " ");
            }
            cout << "\n";
        }
    }
    return 0;
}