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

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:10:46
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,166 bytes
• コンパイル時間: 2,071 ms
• コンパイル使用メモリ: 234,712 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2026-04-18 06:11:16
• 合計ジャッジ時間: 6,706 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <random>
using namespace std;
struct Edge {
    int to;
    int weight;
    int id;
};
int N;
vector<vector<Edge>> adj;
vector<pair<pair<int, int>, int>> edges_output;
vector<int> path_res;
bool found_path;
bool is_square(int n) {
    if (n < 0) return false;
    int root = round(sqrt(n));
    return root * root == n;
}
void dfs(int u, int target, int current_sum, vector<int>& current_path, vector<bool>& vis) {
    if (found_path) return;
    if (u == target) {
        if (is_square(current_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, current_sum + edge.weight, current_path, vis);
            current_path.pop_back();
            vis[edge.to] = false;
        }
    }
}
bool check_all_pairs() {
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            found_path = false;
            vector<bool> vis(N + 1, false);
            vector<int> current_path;
            vis[i] = true;
            dfs(i, j, 0, current_path, vis);
            if (!found_path) return false;
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N)) return 0;
    vector<int> even_weights;
    for (int i = 2; i <= 200; i += 2) {
        even_weights.push_back(i);
    }
    mt19937 rng(1337);
    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;
            vector<bool> vis(N + 1, false);
            vector<int> current_path;
            vis[i] = true;
            dfs(i, j, 0, current_path, vis);
            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;
}