結果

問題 No.1399 すごろくで世界旅行 (構築)
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:07:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,607 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 83,968 KB
最終ジャッジ日時 2025-05-14 13:09:29
合計ジャッジ時間 27,432 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to handle input reading efficiently
def get_ints():
    """Reads a line from stdin and returns a map object of integers."""
    return map(int, sys.stdin.readline().strip().split())

def solve():
    """Solves the Sugoroku World Travel problem."""
    V, D = get_ints()

    # Initialize adjacency matrix with zeros.
    # We use 0-based indexing for vertices (0 to V-1).
    adj = [[0] * V for _ in range(V)]

    # Handle base cases V=1 and V=2
    if V == 1:
        # The problem states "must move". With only one vertex, the only possible move
        # is a self-loop (edge 1 to 1). However, the example V=3 output has E_ii=0.
        # If E_ii=0 is strictly enforced, V=1 is impossible because there is nowhere to move.
        # Assuming V>=3 is guaranteed by problem constraints or impossible cases are handled leniently.
        # Outputting [[0]] represented as a single line string "0".
        print("0")
        return

    if V == 2:
        # The only connected graph is K2 (edge between 1 and 2).
        # The adjacency matrix is [[0, 1], [1, 0]]. This graph is bipartite.
        # In a bipartite graph, path lengths between vertices in the same partition must be even,
        # and path lengths between vertices in different partitions must be odd.
        # Thus, for any D, (E^D)_ij will be 0 for some pairs (i,j).
        # For example, if D is even, (E^D)_12 = 0. If D is odd, (E^D)_11 = 0.
        # The condition (E^D)_ij > 0 for all i,j cannot be satisfied.
        # V=2 is impossible under the constraint E_ii=0.
        # Outputting K2's matrix as a placeholder or based on minimal structure requirement.
        adj[0][1] = 1
        adj[1][0] = 1
        # Print the resulting matrix
        for i in range(V):
             print("".join(map(str, adj[i])))
        return

    # Main logic for V >= 3
    # We need a connected, non-bipartite graph with minimum edges.
    # The minimum number of edges for such a graph is V.
    # We construct such a graph.
    if V % 2 == 1:
        # V is odd. The cycle graph C_V is connected, non-bipartite, and has V edges.
        # Connect vertex i to (i+1) mod V for all i.
        for i in range(V):
            neighbor = (i + 1) % V
            adj[i][neighbor] = 1
            adj[neighbor][i] = 1 # Symmetric edge
    else: # V is even and V >= 4
        # V is even. C_V is bipartite.
        # We construct a graph with V edges that is connected and non-bipartite.
        # One such graph consists of an odd cycle C_{V-1} using vertices 0 to V-2,
        # and attaching the last vertex V-1 to vertex 0.
        # Since V is even, V-1 is odd. C_{V-1} is an odd cycle, making the graph non-bipartite.
        # Total edges = (V-1) edges for C_{V-1} + 1 edge (0, V-1) = V edges.
        
        # Build C_{V-1} on vertices 0..V-2.
        # Need V-1 >= 3 for an odd cycle. Since V is even and V >= 4, V-1 is odd and >= 3. This is valid.
        for i in range(V - 1):
            # Compute neighbor in the cycle 0..V-2
            neighbor = (i + 1) % (V - 1)
            adj[i][neighbor] = 1
            adj[neighbor][i] = 1 # Symmetric edge
        
        # Add edge connecting vertex 0 to vertex V-1
        # This connects the V-th vertex (index V-1) to the cycle vertex 0.
        adj[0][V - 1] = 1
        adj[V - 1][0] = 1 # Symmetric edge

    # Print the final adjacency matrix row by row.
    # Each row is printed as a string of 0s and 1s without spaces.
    for i in range(V):
        print("".join(map(str, adj[i])))

# Run the solve function to process input and produce output.
solve()
0