結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 02:37:19
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,986 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 262 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 89,856 KB
最終ジャッジ日時 2026-04-18 02:37:43
合計ジャッジ時間 5,368 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 3 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    
    is_sq = [False] * 40001
    for i in range(1, 201):
        is_sq[i * i] = True
        
    W = [0] * (N + 1)
    E = [0] * (N + 1)
    used = [False] * 201
    
    def dfs(k, current_S):
        if k == N + 1:
            return True
            
        for w in range(1, 201):
            if used[w]:
                continue
            
            S_k = current_S + w
            
            if k == 2:
                used[w] = True
                W[1] = w
                if dfs(k + 1, S_k):
                    return True
                used[w] = False
                continue
                
            for e in range(1, 201):
                if w == e or used[e]:
                    continue
                
                ok = True
                for i in range(1, k):
                    path_found = False
                    
                    dist_path = S_k - (current_S - sum(W[m] for m in range(i, k-1))) if i < k-1 else w
                    if i == 1:
                        dist_path = S_k
                    
                    if is_sq[dist_path]:
                        path_found = True
                    else:
                        if i == 1:
                            if is_sq[e]:
                                path_found = True
                        elif i == 2:
                            if is_sq[W[1] + e]:
                                path_found = True
                            elif is_sq[dist_path]:
                                path_found = True
                        else:
                            dist_i = sum(W[m] for m in range(1, i))
                            if is_sq[dist_i + e]:
                                path_found = True
                            elif is_sq[E[i] + S_k]:
                                path_found = True
                            elif is_sq[E[i] + e]:
                                path_found = True
                                
                    if not path_found:
                        ok = False
                        break
                        
                if ok:
                    used[w] = True
                    used[e] = True
                    W[k-1] = w
                    E[k] = e
                    if dfs(k + 1, S_k):
                        return True
                    used[w] = False
                    used[e] = False
                    
        return False

    dfs(2, 0)
    
    edges = []
    edge_idx = {}
    
    for i in range(1, N):
        edges.append((i, i + 1, W[i]))
        edge_idx[(i, i + 1)] = len(edges)
        edge_idx[(i + 1, i)] = len(edges)
        
    for i in range(3, N + 1):
        edges.append((1, i, E[i]))
        edge_idx[(1, i)] = len(edges)
        edge_idx[(i, 1)] = len(edges)
        
    M = len(edges)
    print(M)
    for i, (u, v, c) in enumerate(edges):
        print(f"{u} {v} {c}")
        
    adj = [[] for _ in range(N + 1)]
    for i, (u, v, c) in enumerate(edges):
        idx = i + 1
        adj[u].append((v, c, idx))
        adj[v].append((u, c, idx))
        
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            queue = [(i, 0, [], [False] * (N + 1))]
            queue[0][3][i] = True
            ans_path = []
            
            while queue:
                curr, dist, path, visited = queue.pop(0)
                if curr == j and is_sq[dist]:
                    ans_path = path
                    break
                    
                for nxt, c, idx in adj[curr]:
                    if not visited[nxt]:
                        nxt_visited = list(visited)
                        nxt_visited[nxt] = True
                        queue.append((nxt, dist + c, path + [idx], nxt_visited))
                        
            print(len(ans_path))
            print(*ans_path)

solve()
0