結果
問題 | No.826 連絡網 |
ユーザー | rlangevin |
提出日時 | 2023-02-08 08:56:51 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,176 bytes |
コンパイル時間 | 457 ms |
コンパイル使用メモリ | 87,252 KB |
実行使用メモリ | 288,684 KB |
最終ジャッジ日時 | 2023-09-20 02:33:39 |
合計ジャッジ時間 | 19,714 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 95 ms
71,832 KB |
testcase_01 | AC | 94 ms
71,836 KB |
testcase_02 | AC | 105 ms
77,452 KB |
testcase_03 | AC | 123 ms
77,708 KB |
testcase_04 | AC | 123 ms
78,124 KB |
testcase_05 | AC | 120 ms
77,940 KB |
testcase_06 | AC | 119 ms
78,276 KB |
testcase_07 | AC | 122 ms
78,124 KB |
testcase_08 | AC | 120 ms
78,128 KB |
testcase_09 | AC | 125 ms
78,172 KB |
testcase_10 | AC | 114 ms
78,188 KB |
testcase_11 | AC | 121 ms
77,684 KB |
testcase_12 | AC | 1,100 ms
224,488 KB |
testcase_13 | AC | 473 ms
131,132 KB |
testcase_14 | AC | 845 ms
186,752 KB |
testcase_15 | AC | 171 ms
88,376 KB |
testcase_16 | AC | 629 ms
148,092 KB |
testcase_17 | AC | 477 ms
131,376 KB |
testcase_18 | AC | 451 ms
121,816 KB |
testcase_19 | AC | 1,294 ms
251,316 KB |
testcase_20 | AC | 1,420 ms
251,316 KB |
testcase_21 | AC | 126 ms
78,112 KB |
testcase_22 | AC | 583 ms
133,040 KB |
testcase_23 | AC | 609 ms
148,416 KB |
testcase_24 | AC | 326 ms
108,084 KB |
testcase_25 | TLE | - |
testcase_26 | AC | 400 ms
115,248 KB |
testcase_27 | AC | 1,127 ms
231,116 KB |
testcase_28 | AC | 1,108 ms
196,616 KB |
testcase_29 | AC | 563 ms
131,288 KB |
testcase_30 | AC | 1,670 ms
285,824 KB |
testcase_31 | AC | 667 ms
145,604 KB |
ソースコード
from collections import deque def bfs(G, s, N): Q = deque([]) dist = [-1] * N par = [-1] * N sz = [1] * N dist[s] = 0 rev = [0] * N for u in G[s]: par[u] = s dist[u] = 1 sz[u] += sz[s] Q.append(u) while Q: u = Q.popleft() for v in G[u]: if dist[v] != -1: continue if v < u: rev[v] = rev[u] + 1 else: rev[v] = rev[u] dist[v] = dist[u] + 1 par[v] = u sz[v] += sz[u] Q.append(v) return dist from math import ceil, sqrt def Sieve(n): lst = [True] * (n + 1) S = set() for i in range(2, ceil(sqrt(n)) + 1): if lst[i]: for j in range(2 * i, n + 1, i): lst[j] = False for i in range(2, n + 1): if lst[i]: S.add(i) return S N, P = map(int, input().split()) G = [[] for i in range(N + 1)] for i in Sieve(N): for j in range(i, N + 1, i): if j + i <= N: G[j].append(j + i) G[j + i].append(j) D = bfs(G, P, N + 1) print(N + 1 - D.count(-1))