結果

問題 No.1400 すごろくで世界旅行
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:52:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,945 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 403,912 KB
最終ジャッジ日時 2025-06-12 13:53:40
合計ジャッジ時間 7,965 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 MLE * 2 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    V, D = map(int, sys.stdin.readline().split())
    E = []
    for _ in range(V):
        s = sys.stdin.readline().strip()
        row = [int(c) for c in s]
        E.append(row)
    
    # Build adjacency list
    adj = [[] for _ in range(V)]
    for i in range(V):
        for j in range(V):
            if E[i][j] == 1:
                adj[i].append(j)
    
    # Check if the graph is strongly connected using Kosaraju's algorithm
    visited = [False] * V
    order = []
    
    def dfs(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if visited[node]:
                continue
            visited[node] = True
            stack.append((node, True))
            for v in adj[node]:
                if not visited[v]:
                    stack.append((v, False))
    
    for u in range(V):
        if not visited[u]:
            dfs(u)
    
    reverse_adj = [[] for _ in range(V)]
    for u in range(V):
        for v in adj[u]:
            reverse_adj[v].append(u)
    
    visited = [False] * V
    component = [0] * V
    label = 0
    
    def reverse_dfs(u, label):
        stack = [u]
        visited[u] = True
        component[u] = label
        while stack:
            node = stack.pop()
            for v in reverse_adj[node]:
                if not visited[v]:
                    visited[v] = True
                    component[v] = label
                    stack.append(v)
    
    for u in reversed(order):
        if not visited[u]:
            reverse_dfs(u, label)
            label += 1
    
    if label != 1:
        print("No")
        return
    
    # Check bipartite
    color = [-1] * V
    is_bip = True
    start = 0
    color[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if color[v] == -1:
                color[v] = color[u] ^ 1
                q.append(v)
            elif color[v] == color[u]:
                is_bip = False
                break
        if not is_bip:
            break
    
    if is_bip:
        print("No")
        return
    
    # Check if D is large enough
    if D >= 2 * V - 2:
        print("Yes")
        return
    
    # Compute diameter
    max_diameter = 0
    for u in range(V):
        dist = [-1] * V
        q = deque([u])
        dist[u] = 0
        current_max = 0
        while q:
            node = q.popleft()
            for v in adj[node]:
                if dist[v] == -1:
                    dist[v] = dist[node] + 1
                    current_max = max(current_max, dist[v])
                    q.append(v)
        max_diameter = max(max_diameter, current_max)
        if max_diameter > D:
            print("No")
            return
    
    print("Yes")

if __name__ == "__main__":
    main()
0