結果
問題 |
No.812 Change of Class
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()))