結果

問題 No.812 Change of Class
ユーザー ttrttr
提出日時 2020-06-21 18:40:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,394 ms / 4,000 ms
コード長 929 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 87,048 KB
実行使用メモリ 173,988 KB
最終ジャッジ日時 2023-09-16 18:38:57
合計ジャッジ時間 52,621 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 368 ms
107,552 KB
testcase_01 AC 180 ms
80,152 KB
testcase_02 AC 281 ms
92,812 KB
testcase_03 AC 423 ms
117,368 KB
testcase_04 AC 373 ms
110,356 KB
testcase_05 AC 2,360 ms
144,196 KB
testcase_06 AC 2,394 ms
140,932 KB
testcase_07 AC 94 ms
93,904 KB
testcase_08 AC 82 ms
75,852 KB
testcase_09 AC 2,111 ms
140,040 KB
testcase_10 AC 2,074 ms
138,924 KB
testcase_11 AC 163 ms
129,488 KB
testcase_12 AC 1,225 ms
125,292 KB
testcase_13 AC 73 ms
71,100 KB
testcase_14 AC 73 ms
71,248 KB
testcase_15 AC 1,552 ms
123,472 KB
testcase_16 AC 295 ms
81,420 KB
testcase_17 AC 1,403 ms
120,564 KB
testcase_18 AC 1,174 ms
111,996 KB
testcase_19 AC 1,320 ms
117,008 KB
testcase_20 AC 2,175 ms
141,788 KB
testcase_21 AC 984 ms
107,780 KB
testcase_22 AC 622 ms
93,072 KB
testcase_23 AC 316 ms
80,824 KB
testcase_24 AC 310 ms
81,620 KB
testcase_25 AC 507 ms
89,940 KB
testcase_26 AC 1,943 ms
133,140 KB
testcase_27 AC 1,503 ms
124,844 KB
testcase_28 AC 1,185 ms
114,552 KB
testcase_29 AC 513 ms
87,664 KB
testcase_30 AC 1,392 ms
120,304 KB
testcase_31 AC 1,329 ms
118,432 KB
testcase_32 AC 647 ms
96,144 KB
testcase_33 AC 1,587 ms
125,104 KB
testcase_34 AC 272 ms
80,676 KB
testcase_35 AC 396 ms
87,496 KB
testcase_36 AC 302 ms
81,360 KB
testcase_37 AC 749 ms
98,280 KB
testcase_38 AC 133 ms
100,840 KB
testcase_39 AC 751 ms
97,820 KB
testcase_40 AC 289 ms
83,024 KB
testcase_41 AC 122 ms
97,888 KB
testcase_42 AC 1,525 ms
118,480 KB
testcase_43 AC 287 ms
98,640 KB
testcase_44 AC 1,182 ms
106,668 KB
testcase_45 AC 295 ms
80,984 KB
testcase_46 AC 270 ms
103,804 KB
testcase_47 AC 1,028 ms
106,464 KB
testcase_48 AC 922 ms
112,160 KB
testcase_49 AC 436 ms
87,280 KB
testcase_50 AC 159 ms
77,868 KB
testcase_51 AC 378 ms
90,264 KB
testcase_52 AC 513 ms
104,980 KB
testcase_53 AC 368 ms
84,168 KB
testcase_54 AC 343 ms
82,668 KB
testcase_55 AC 972 ms
142,840 KB
testcase_56 AC 1,142 ms
158,804 KB
testcase_57 AC 1,169 ms
162,780 KB
testcase_58 AC 634 ms
119,008 KB
testcase_59 AC 1,351 ms
173,988 KB
testcase_60 AC 73 ms
71,268 KB
testcase_61 AC 73 ms
71,040 KB
testcase_62 AC 73 ms
71,072 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
def dijkstra(s):
    inf = 10**9
    d = [inf]*N
    used = [0]*N
    h = [s]
    while h:
        temp = heapq.heappop(h)
        dist = temp//N
        u = temp%N
        if used[u] == 1:
            continue
        used[u] = 1
        d[u] = dist
        for v in E[u]:
            if used[v] == 1:
                continue
            heapq.heappush(h, (dist+1)*N+v)
    return d


N,M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    p,q = map(int, input().split())
    E[p-1].append(q-1)
    E[q-1].append(p-1)

Q = int(input())
for _ in range(Q):
    a = int(input())
    d = dijkstra(a-1)
    num = -1
    dist = 0
    for i in range(N):
        if d[i] == 10**9:
            continue
        dist = max(dist, d[i]-1)
        num += 1
    cnt = 0
    for i in range(dist+1):
        if cnt >= dist:
            day = i
            break
        cnt += 1<<i
    print(num, day)
0