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

• 問題: No.3506 All Distance is Square Number
• ユーザー: Naru820
• 提出日時: 2026-03-17 22:52:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,263 bytes
• コンパイル時間: 2,553 ms
• コンパイル使用メモリ: 216,240 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2026-04-17 19:41:52
• 合計ジャッジ時間: 11,797 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
other	WA * 3 TLE * 1 -- * 25

ソースコード

//gemini3.1pro
#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <random>

using namespace std;

// 辺の構造体
struct Edge {
    int to;
    int weight;
    int id;
};

// 平方数判定
bool is_square(int n) {
    if (n < 0) return false;
    int r = round(sqrt(n));
    return r * r == n;
}

int N;
vector<vector<Edge>> adj;
vector<bool> visited;
vector<int> best_path;

// 深さ制限付きDFS (単純パスの探索)
bool dfs(int u, int target, int sum, int depth, int max_depth, vector<int>& path) {
    if (u == target) {
        if (is_square(sum)) {
            best_path = path;
            return true;
        }
    }
    if (depth == max_depth) return false;

    for (auto& edge : adj[u]) {
        int v = edge.to;
        if (!visited[v]) {
            visited[v] = true;
            path.push_back(edge.id);
            if (dfs(v, target, sum + edge.weight, depth + 1, max_depth, path)) return true;
            path.pop_back();
            visited[v] = false;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int M = 2 * N - 3;
    if (N == 2) M = 1;

    // 乱数生成器
    mt19937 rng(1337);

    while (true) {
        // 1から200の重みをシャッフル
        vector<int> weights(200);
        iota(weights.begin(), weights.end(), 1);
        shuffle(weights.begin(), weights.end(), rng);

        adj.assign(N, vector<Edge>());
        
        struct EdgeDef { int u, v, w; };
        vector<EdgeDef> edges;

        // グラフの構築 (2つの中心 0, 1 と、それに繋がる葉)
        if (N == 2) {
            edges.push_back({0, 1, weights[0]});
        } else {
            edges.push_back({0, 1, weights[0]});
            int w_idx = 1;
            for (int i = 2; i < N; ++i) {
                edges.push_back({0, i, weights[w_idx++]});
                edges.push_back({1, i, weights[w_idx++]});
            }
        }

        // 隣接リストの構築
        for (int i = 0; i < M; ++i) {
            adj[edges[i].u].push_back({edges[i].v, edges[i].w, i});
            adj[edges[i].v].push_back({edges[i].u, edges[i].w, i});
        }

        bool all_ok = true;
        vector<vector<int>> ans_paths;

        // 全てのペア (i, j) について平方数パスが存在するか検証
        for (int i = 0; i < N && all_ok; ++i) {
            for (int j = i + 1; j < N && all_ok; ++j) {
                bool found = false;
                // 反復深化DFS (短いパスから優先して探すことで高速化)
                for (int d = 1; d <= 5; ++d) {
                    visited.assign(N, false);
                    visited[i] = true;
                    vector<int> current_path;
                    if (dfs(i, j, 0, 0, d, current_path)) {
                        ans_paths.push_back(best_path);
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    all_ok = false;
                }
            }
        }

        // 全てのペアで条件を満たした場合は出力して終了
        if (all_ok) {
            // パスの長さを出力に含める一般的な形式
            for (int i = 0; i < M; ++i) {
                // 辺の出力: u v 重み
                // ※ もし辺の出力フォーマットの指定があれば適宜書き換えてください
                // (問題文ではグラフの出力と Qi,j の出力が求められています)
            }
            
            // 以下、辺の情報と各ペアのパスを出力します
            // M, 次に各辺(u, v, c)
            cout << M << "\n";
            for(int i=0; i<M; ++i) {
                cout << edges[i].u << " " << edges[i].v << " " << edges[i].w << "\n";
            }
            
            // パス Qi,j の出力 (パスの長さ k と、そのあとに辺の番号 e_i を出力)
            for (auto& p : ans_paths) {
                cout << p.size();
                for (int e : p) cout << " " << e;
                cout << "\n";
            }
            break;
        }
    }
    return 0;
}