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

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

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

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <cmath>
using namespace std;
int N;
int W_edge[105];
bool used_even[205];
int even_candidates[105];
int num_even;
int adj_to[105][5];
int adj_weight[105][5];
int adj_id[105][5];
int adj_deg[105];
bool is_sq[40005];
int current_path[105];
int path_len;
vector<int> found_path_res;
bool vis[105];
int dfs_steps;
const int MAX_DFS_STEPS = 4000;
int backtrack_calls;
const int MAX_CALLS = 50000;
inline void add_edge(int u, int v, int w, int id) {
    adj_to[u][adj_deg[u]] = v;
    adj_weight[u][adj_deg[u]] = w;
    adj_id[u][adj_deg[u]] = id;
    adj_deg[u]++;
    adj_to[v][adj_deg[v]] = u;
    adj_weight[v][adj_deg[v]] = w;
    adj_id[v][adj_deg[v]] = id;
    adj_deg[v]++;
}
inline void remove_edge(int u, int v) {
    adj_deg[u]--;
    adj_deg[v]--;
}
bool has_square_path(int u, int target, int max_node, int current_sum, bool limit_steps) {
    if (limit_steps) {
        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.assign(current_path, current_path + path_len);
            return true;
        }
        return false;
    }
    int deg = adj_deg[u];
    int order[4] = {0, 1, 2, 3};
    for(int i = 0; i < deg; ++i) {
        for(int j = i + 1; j < deg; ++j) {
            if (abs(adj_to[u][order[i]] - target) > abs(adj_to[u][order[j]] - target)) {
                int tmp = order[i];
                order[i] = order[j];
                order[j] = tmp;
            }
        }
    }
    for(int i = 0; i < deg; ++i) {
        int idx = order[i];
        int v = adj_to[u][idx];
        if (v > max_node || vis[v]) continue;
        int w = adj_weight[u][idx];
        int id = adj_id[u][idx];
        vis[v] = true;
        current_path[path_len++] = id;
        if (has_square_path(v, target, max_node, current_sum + w, limit_steps)) return true;
        path_len--;
        vis[v] = 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 i = 0; i < num_even; ++i) {
        int w = even_candidates[i];
        if (used_even[w]) continue;
        W_edge[k] = w;
        used_even[w] = true;
        add_edge(k, new_node, w, N - 1 + k);
        bool valid = true;
        for (int start = 1; start < new_node; ++start) {
            for(int v = 1; v <= new_node; ++v) vis[v] = false;
            vis[new_node] = true;
            dfs_steps = 0;
            path_len = 0;
            if (!has_square_path(new_node, start, new_node, 0, true)) {
                valid = false;
                break;
            }
        }
        if (valid) {
            if (backtrack(k + 1)) return true;
        }
        used_even[w] = false;
        remove_edge(k, new_node);
        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;
    num_even = 0;
    for (int i = 2; i <= 200; i += 2) {
        even_candidates[num_even++] = i;
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    while (true) {
        shuffle(even_candidates, even_candidates + num_even, rng);
        for(int i = 0; i <= 200; ++i) used_even[i] = false;
        for(int i = 1; i <= N; ++i) adj_deg[i] = 0;
        for (int i = 1; i < N; ++i) {
            add_edge(i, i + 1, 2 * i - 1, 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_edge[k] << "\n";
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            for(int v = 1; v <= N; ++v) vis[v] = false;
            vis[j] = true;
            path_len = 0;
            found_path_res.clear();
            has_square_path(j, i, j, 0, false);
            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;
}