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

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:32:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,990 bytes
• コンパイル時間: 4,276 ms
• コンパイル使用メモリ: 275,224 KB
• 実行使用メモリ: 11,556 KB
• 最終ジャッジ日時: 2026-04-18 06:32:36
• 合計ジャッジ時間: 7,783 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

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

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
struct Edge {
    int to;
    int weight;
    int id;
};
int N;
vector<int> W;
vector<bool> used_even;
vector<int> even_candidates;
bool is_sq[40005];
vector<vector<Edge>> adj;
int dfs_steps;
vector<int> current_path;
vector<int> found_path_res;
int backtrack_calls;
const int MAX_CALLS = 2000;
const int MAX_DFS_STEPS = 500;
bool has_square_path(int u, int target, int max_node, int current_sum, vector<bool>& vis) {
    dfs_steps++;
    if (dfs_steps > MAX_DFS_STEPS) return false;
    if (current_sum >= 40005) return false;
    if (u == target) {
        if (is_sq[current_sum]) {
            found_path_res = current_path;
            return true;
        }
        return false;
    }
    vector<Edge> neighbors = adj[u];
    sort(neighbors.begin(), neighbors.end(), [&](const Edge& a, const Edge& b) {
        return abs(a.to - target) < abs(b.to - target);
    });
    for (const auto& edge : neighbors) {
        if (edge.to <= max_node && !vis[edge.to]) {
            vis[edge.to] = true;
            current_path.push_back(edge.id);
            if (has_square_path(edge.to, target, max_node, current_sum + edge.weight, vis)) {
                return true;
            }
            current_path.pop_back();
            vis[edge.to] = false;
        }
    }
    return false;
}
bool get_output_path(int u, int target, int max_node, int current_sum, vector<bool>& vis) {
    if (current_sum >= 40005) return false;
    if (u == target) {
        if (is_sq[current_sum]) {
            found_path_res = current_path;
            return true;
        }
        return false;
    }
    vector<Edge> neighbors = adj[u];
    sort(neighbors.begin(), neighbors.end(), [&](const Edge& a, const Edge& b) {
        return abs(a.to - target) < abs(b.to - target);
    });
    for (const auto& edge : neighbors) {
        if (edge.to <= max_node && !vis[edge.to]) {
            vis[edge.to] = true;
            current_path.push_back(edge.id);
            if (get_output_path(edge.to, target, max_node, current_sum + edge.weight, vis)) {
                return true;
            }
            current_path.pop_back();
            vis[edge.to] = false;
        }
    }
    return false;
}
bool backtrack(int k) {
    backtrack_calls++;
    if (backtrack_calls > MAX_CALLS) return false;
    if (k == N - 1) return true;
    int new_node = k + 2;
    for (int w : even_candidates) {
        if (used_even[w]) continue;
        W[k] = w;
        used_even[w] = true;
        int edge_id = N - 1 + k;
        adj[k].push_back({new_node, w, edge_id});
        adj[new_node].push_back({k, w, edge_id});
        bool valid = true;
        for (int i = 1; i < new_node; ++i) {
            vector<bool> vis(N + 1, false);
            vis[new_node] = true;
            dfs_steps = 0;
            current_path.clear();
            if (!has_square_path(new_node, i, new_node, 0, vis)) {
                valid = false;
                break;
            }
        }
        if (valid) {
            if (backtrack(k + 1)) return true;
        }
        used_even[w] = false;
        adj[k].pop_back();
        adj[new_node].pop_back();
        if (backtrack_calls > MAX_CALLS) return false;
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N)) return 0;
    for (int i = 0; i < 40005; ++i) is_sq[i] = false;
    for (int i = 1; i * i < 40005; ++i) is_sq[i * i] = true;
    for (int i = 2; i <= 200; i += 2) even_candidates.push_back(i);
    used_even.assign(205, false);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    while (true) {
        shuffle(even_candidates.begin(), even_candidates.end(), rng);
        fill(used_even.begin(), used_even.end(), false);
        W.assign(N, 0);
        adj.assign(N + 1, vector<Edge>());
        for (int i = 1; i < N; ++i) {
            int w = 2 * i - 1;
            adj[i].push_back({i + 1, w, i});
            adj[i + 1].push_back({i, w, i});
        }
        backtrack_calls = 0;
        if (backtrack(1)) {
            break;
        }
    }
    cout << (2 * N - 3) << "\n";
    for (int i = 1; i < N; ++i) {
        cout << i << " " << (i + 1) << " " << (2 * i - 1) << "\n";
    }
    for (int k = 1; k <= N - 2; ++k) {
        cout << k << " " << (k + 2) << " " << W[k] << "\n";
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            vector<bool> vis(N + 1, false);
            vis[j] = true;
            current_path.clear();
            found_path_res.clear();
            get_output_path(j, i, j, 0, vis);
            cout << found_path_res.size() << "\n";
            for (int k = (int)found_path_res.size() - 1; k >= 0; --k) {
                cout << found_path_res[k] << (k == 0 ? "" : " ");
            }
            cout << "\n";
        }
    }
    return 0;
}