結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-06-14 18:57:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 976 ms / 4,000 ms |
コード長 | 897 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,088 KB |
実行使用メモリ | 192,460 KB |
最終ジャッジ日時 | 2024-06-12 21:15:15 |
合計ジャッジ時間 | 22,472 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
from collections import deque import sys sys.setrecursionlimit(200000) n, m = map(int, input().split()) info = [list(map(int, input().split())) for i in range(m)] q = int(input()) a = [int(input()) for i in range(q)] tree = [[] for i in range(n)] for i in range(m): tree[info[i][0] - 1].append(info[i][1] - 1) tree[info[i][1] - 1].append(info[i][0] - 1) def bfs(a): visited = [False]*n cnt = 0 q = deque([]) q.append([0, a]) visited[a] = True while q: times, pos = q.popleft() for next_pos in tree[pos]: if not visited[next_pos]: visited[next_pos] = True cnt += 1 q.append([times + 1, next_pos]) if times == 0 or times == 1: day = 0 else: day = (times-1).bit_length() return cnt, day for i in range(q): ans1, ans2 = bfs(a[i] - 1) print(ans1, ans2)