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

• 問題: No.3506 All Distance is Square Number
• ユーザー: gojoxd
• 提出日時: 2026-04-18 19:15:39
• 言語: C (gcc 15.2.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,489 bytes
• コンパイル時間: 430 ms
• コンパイル使用メモリ: 45,056 KB
• 実行使用メモリ: 8,448 KB
• 最終ジャッジ日時: 2026-04-18 19:16:07
• 合計ジャッジ時間: 9,414 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

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

ソースコード

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

#define MAX_N 105
#define MAX_WEIGHT 205

int N;
int match[MAX_WEIGHT]; 
bool vis[MAX_WEIGHT];

typedef struct {
    int v, w, id;
} Adj;

Adj adj_list[MAX_N][MAX_N];
int degree[MAX_N];

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];
int dfs_steps = 0;

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

// Bipartite matching to find a valid distinct even weight for each skip edge
bool dfs_match(int i) {
    for (int S = 3; S <= 19; S += 2) { // Try odd squares: 9, 25, 49... 361
        int w = S * S - (2 * i - 1);
        if (w >= 2 && w <= 200 && w % 2 == 0) {
            if (!vis[w]) {
                vis[w] = true;
                if (match[w] == 0 || dfs_match(match[w])) {
                    match[w] = i;
                    return true;
                }
            }
        }
    }
    return false;
}

// Fast DFS to fetch the path for output
bool dfs_path(int u, int target, int sum, int depth) {
    dfs_steps++;
    if (dfs_steps > 150000) return false; // Safety cutoff to reshuffle and prevent deep stalling
    
    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;
    }
    
    visited[u] = true;
    for (int i = 0; i < degree[u]; i++) {
        int v = adj_list[u][i].v;
        int w = adj_list[u][i].w;
        if (!visited[v]) {
            if (dfs_path(v, target, sum + w, depth + 1)) {
                visited[u] = false;
                return true;
            }
        }
    }
    visited[u] = false;
    return false;
}

int get_edge_id(int u, int v) {
    for (int i = 0; i < degree[u]; i++) {
        if (adj_list[u][i].v == v) return adj_list[u][i].id;
    }
    return -1;
}

int main() {
    if (scanf("%d", &N) != 1) return 0;
    
    srand(1337);
    
    // Assign distinct even weights deterministically using Hopcroft-Karp style matching
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= N - 2; i++) {
        memset(vis, 0, sizeof(vis));
        dfs_match(i); 
    }
    
    M = 0;
    // 1. Build the Spine (Consecutive Odd Weights)
    for (int i = 1; i < N; i++) {
        int w = 2 * i - 1;
        edges[M] = (Edge){i, i + 1, w};
        
        adj_list[i][degree[i]++] = (Adj){i + 1, w, M + 1};
        adj_list[i + 1][degree[i + 1]++] = (Adj){i, w, M + 1};
        M++;
    }
    
    // 2. Build the Skip Edges (Calculated Even Weights)
    for (int i = 1; i <= N - 2; i++) {
        int w = 0;
        for (int j = 2; j <= 200; j += 2) {
            if (match[j] == i) {
                w = j;
                break;
            }
        }
        
        edges[M] = (Edge){i, i + 2, w};
        adj_list[i][degree[i]++] = (Adj){i + 2, w, M + 1};
        adj_list[i + 2][degree[i + 2]++] = (Adj){i, w, M + 1};
        M++;
    }
    
    // Print Output Graph Structure
    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);
    }
    
    // Extract Paths
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            
            while (true) {
                dfs_steps = 0;
                best_path_len = 0;
                memset(visited, 0, sizeof(visited));
                
                if (dfs_path(i, j, 0, 0)) break;
                
                // If it stalled, randomly shuffle adjacency lists to traverse a new route instantly
                for (int u = 1; u <= N; u++) {
                    for (int k = 0; k < degree[u]; k++) {
                        int r = k + rand() % (degree[u] - k);
                        Adj temp = adj_list[u][k];
                        adj_list[u][k] = adj_list[u][r];
                        adj_list[u][r] = temp;
                    }
                }
            }
            
            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;
}