結果

問題 No.812 Change of Class
コンテスト
ユーザー maspy
提出日時 2020-02-07 10:43:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,728 ms / 4,000 ms
コード長 870 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 89,004 KB
最終ジャッジ日時 2024-06-12 21:55:01
合計ジャッジ時間 75,508 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from scipy.sparse.csgraph import connected_components, dijkstra
from scipy.sparse import csr_matrix

data = np.fromstring(read(), np.int64, sep=' ')

N, M = data[:2]
UV = data[2:2+M+M]
U = UV[::2]
V = UV[1::2]
Q = data[2+M+M]
A = data[2+M+M+1:]

graph = csr_matrix((np.ones_like(U), (U, V)), (N+1, N+1))

_, comp = connected_components(graph)
comp_size = np.bincount(comp)

dist = dijkstra(graph, directed=False, indices=A)

dist[dist == np.inf] = 0
dist = dist.max(axis=1).astype(int)

sizes = comp_size[comp[A]]

def gen_answers():
    for s, d in zip(sizes, dist):
        if d <= 1:
            day = 0
        else:
            day = int(d-1).bit_length()
        yield '{} {}'.format(s - 1, day)

print('\n'.join(gen_answers()))
0