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

• 問題: No.3506 All Distance is Square Number
• ユーザー: gojoxd
• 提出日時: 2026-04-18 19:02:22
• 言語: C (gcc 15.2.0)
• 結果: WA
• 実行時間: -
• コード長: 3,666 bytes
• コンパイル時間: 1,129 ms
• コンパイル使用メモリ: 45,560 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-18 19:02:34
• 合計ジャッジ時間: 11,051 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	AC * 3 WA * 26

ソースコード

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

#define MAX_N 105
#define MAX_WEIGHT 200

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

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

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

int path_count = 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;
}

void dfs(int u, int target, int current_sum, int depth) {
    if (best_path_len > 0) return; // Already found a valid path
    
    current_path[depth] = u;
    if (u == target) {
        if (is_square(current_sum)) {
            best_path_len = depth + 1;
            for (int i = 0; i < best_path_len; i++) {
                best_path[i] = current_path[i];
            }
        }
        return;
    }
    
    visited[u] = true;
    for (int v = 1; v <= N; v++) {
        if (adj[u][v] && !visited[v]) {
            dfs(v, target, current_sum + adj[u][v], depth + 1);
        }
    }
    visited[u] = false;
}

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;
    
    // Step 1: Build the spine with odd weights
    int current_odd = 1;
    for (int i = 1; i < N; i++) {
        edges[M++] = (Edge){i, i + 1, current_odd};
        adj[i][i + 1] = current_odd;
        adj[i + 1][i] = current_odd;
        used_weight[current_odd] = true;
        
        if (i == 1 && current_odd == 1) {
            // Adjust to ensure we don't use 1 if we need variations
            // But 1, 3, 5... works perfectly for the spine.
        }
        current_odd += 2;
    }
    
    // Step 2: Add random edges to satisfy remaining paths using backtracking/random search
    srand(1337); 
    
    for (int i = 3; i <= N; i++) {
        bool covered = false;
        // Check if all pairs (j, i) where j < i are covered
        for (int attempt = 0; attempt < 500 && !covered; attempt++) {
            int u = (rand() % (i - 1)) + 1;
            int w = (rand() % MAX_WEIGHT) + 1;
            
            if (used_weight[w] || adj[u][i]) continue;
            
            // Temporarily add edge
            adj[u][i] = w;
            adj[i][u] = w;
            
            bool all_ok = true;
            for (int j = 1; j < i; j++) {
                best_path_len = 0;
                dfs(j, i, 0, 0);
                if (best_path_len == 0) {
                    all_ok = false;
                    break;
                }
            }
            
            if (all_ok) {
                edges[M++] = (Edge){u, i, w};
                used_weight[w] = true;
                covered = true;
            } else {
                // Revert
                adj[u][i] = 0;
                adj[i][u] = 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;
            for (int k = 1; k <= N; k++) visited[k] = false;
            dfs(i, j, 0, 0);
            
            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;
}