#1159964 (C) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: gojoxd
• 提出日時: 2026-04-18 19:10:51
• 言語: C (gcc 15.2.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,228 bytes
• コンパイル時間: 317 ms
• コンパイル使用メモリ: 46,720 KB
• 実行使用メモリ: 8,320 KB
• 最終ジャッジ日時: 2026-04-18 19:11:29
• 合計ジャッジ時間: 9,541 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define MAX_N 105
#define MAX_WEIGHT 205

int N;
int adj[MAX_N][MAX_N];
bool used_weight[MAX_WEIGHT];

typedef struct {
    int u, v, w;
} Edge;

Edge edges[MAX_N * 2];
int M = 0;

int current_path[MAX_N];
int best_path[MAX_N];
int best_path_len = 0;
bool visited[MAX_N];

bool is_square(int n) {
    if (n < 0) return false;
    int r = (int)round(sqrt(n));
    return r * r == n;
}

int dfs_steps = 0;

// Randomized DFS to search for a valid square-sum simple path
bool dfs(int u, int target, int sum, int depth, int limit) {
    current_path[depth] = u;
    if (u == target) {
        if (is_square(sum)) {
            best_path_len = depth + 1;
            for (int i = 0; i < best_path_len; i++) {
                best_path[i] = current_path[i];
            }
            return true;
        }
        return false;
    }
    
    dfs_steps++;
    if (dfs_steps > limit) return false;

    visited[u] = true;
    
    // Collect and randomize neighbors to prevent getting stuck in deep false branches
    int neighbors[MAX_N], n_count = 0;
    for (int v = 1; v <= N; v++) {
        if (adj[u][v] && !visited[v]) {
            neighbors[n_count++] = v;
        }
    }
    
    for (int i = 0; i < n_count; i++) {
        int r = i + rand() % (n_count - i);
        int temp = neighbors[i];
        neighbors[i] = neighbors[r];
        neighbors[r] = temp;
    }
    
    for (int i = 0; i < n_count; i++) {
        if (dfs(neighbors[i], target, sum + adj[u][neighbors[i]], depth + 1, limit)) {
            visited[u] = false;
            return true;
        }
    }
    
    visited[u] = false;
    return false;
}

// Maps two vertices to their canonical 1-based edge ID
int get_edge_id(int u, int v) {
    for (int i = 0; i < M; i++) {
        if ((edges[i].u == u && edges[i].v == v) || (edges[i].u == v && edges[i].v == u)) {
            return i + 1;
        }
    }
    return -1;
}

int main() {
    if (scanf("%d", &N) != 1) return 0;
    
    srand(1337); 
    
    // Step 1: Build the core spine using consecutive odd weights
    for (int i = 1; i < N; i++) {
        int w = 2 * i - 1;
        edges[M++] = (Edge){i, i + 1, w};
        adj[i][i + 1] = w;
        adj[i + 1][i] = w;
        used_weight[w] = true;
    }
    
    // Step 2: Triangulate the spine by adding skip edges (i, i+2)
    for (int i = 1; i <= N - 2; i++) {
        int evens[100], e_cnt = 0;
        for (int w = 2; w <= 200; w += 2) {
            if (!used_weight[w]) evens[e_cnt++] = w;
        }
        
        // Shuffle the pool of available even numbers
        for (int x = 0; x < e_cnt; x++) {
            int r = x + rand() % (e_cnt - x);
            int t = evens[x]; evens[x] = evens[r]; evens[r] = t;
        }
        
        // HEURISTIC: Prefer a weight W that perfectly makes the adjacent pair (i+1, i+2) a square.
        // The path i+1 -> i -> i+2 has the weight `(2i-1) + W`.
        for (int x = 0; x < e_cnt; x++) {
            if (is_square(evens[x] + 2 * i - 1)) {
                int temp = evens[0];
                evens[0] = evens[x];
                evens[x] = temp;
                break; 
            }
        }

        bool found_W = false;
        for (int idx = 0; idx < e_cnt; idx++) {
            int w = evens[idx];
            adj[i][i + 2] = w;
            adj[i + 2][i] = w;
            
            bool ok = true;
            // Verify all cross-paths ending in the newly added rightmost node (i+2)
            for (int j = 1; j <= i + 1; j++) {
                bool pair_ok = false;
                for (int attempt = 0; attempt < 5; attempt++) {
                    dfs_steps = 0;
                    best_path_len = 0;
                    for (int k = 1; k <= N; k++) visited[k] = false;
                    if (dfs(j, i + 2, 0, 0, 8000)) {
                        pair_ok = true;
                        break;
                    }
                }
                if (!pair_ok) {
                    ok = false;
                    break;
                }
            }
            
            if (ok) {
                edges[M++] = (Edge){i, i + 2, w};
                used_weight[w] = true;
                found_W = true;
                break;
            } else {
                // Backtrack
                adj[i][i + 2] = 0;
                adj[i + 2][i] = 0;
            }
        }
    }
    
    // Output Phase
    printf("%d\n", M);
    for (int i = 0; i < M; i++) {
        printf("%d %d %d\n", edges[i].u, edges[i].v, edges[i].w);
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            best_path_len = 0;
            
            // Loop guarantees we pull the validated square path
            while (true) {
                dfs_steps = 0;
                for (int k = 1; k <= N; k++) visited[k] = false;
                if (dfs(i, j, 0, 0, 100000)) break;
            }
            
            printf("%d", best_path_len - 1);
            for (int k = 0; k < best_path_len - 1; k++) {
                printf(" %d", get_edge_id(best_path[k], best_path[k+1]));
            }
            printf("\n");
        }
    }
    
    return 0;
}