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

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:49:41
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,097 bytes
• コンパイル時間: 3,197 ms
• コンパイル使用メモリ: 232,956 KB
• 実行使用メモリ: 9,856 KB
• 最終ジャッジ日時: 2026-04-18 06:50:17
• 合計ジャッジ時間: 8,837 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
other	AC * 2 WA * 6 TLE * 2 -- * 19

ソースコード

#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 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 = 150;
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) {
    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;
        vis[v] = true;
        current_path[path_len++] = adj_id[u][idx];
        if (has_square_path(v, target, max_node, current_sum + adj_weight[u][idx])) return true;
        path_len--;
        vis[v] = false;
    }
    return false;
}
bool check_all_pairs() {
    for (int d = 1; d < N; ++d) {
        for (int i = 1; i <= N - d; ++i) {
            int j = i + d;
            for(int v = 1; v <= N; ++v) vis[v] = false;
            vis[i] = true;
            dfs_steps = 0;
            path_len = 0;
            if (!has_square_path(i, j, N, 0)) return false;
        }
    }
    return true;
}
mt19937 rng(1337);
bool assign_B(int k) {
    if (k > N - 2) {
        return check_all_pairs();
    }
    int squares[] = {9, 25, 49, 81, 121, 169, 225, 289, 361};
    shuffle(squares, squares + 9, rng);
    for (int S : squares) {
        int w = S - (2 * k - 1);
        if (w >= 2 && w <= 200 && w % 2 == 0 && !used_even[w]) {
            used_even[w] = true;
            W_edge[k] = w;
            add_edge(k, k + 2, w, N - 1 + k);
            if (assign_B(k + 1)) return true;
            remove_edge(k, k + 2);
            used_even[w] = 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 = 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);
    }
    assign_B(1);
    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;
            dfs_steps = 0;
            path_len = 0;
            found_path_res.clear();
            has_square_path(j, i, j, 0);
            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;
}