結果
問題 |
No.826 連絡網
|
ユーザー |
![]() |
提出日時 | 2019-05-03 22:23:41 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,139 bytes |
コンパイル時間 | 277 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 29,568 KB |
最終ジャッジ日時 | 2024-12-31 18:09:43 |
合計ジャッジ時間 | 21,566 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 TLE * 2 |
ソースコード
class UnionFind: def __init__(self, size): self.data = [-1 for _ in range(size)] def find(self, x): if self.data[x] < 0: return x else: self.data[x] = self.find(self.data[x]) return self.data[x] def union(self, x, y): x, y = self.find(x), self.find(y) if x != y: if self.data[y] < self.data[x]: x, y = y, x self.data[x] += self.data[y] self.data[y] = x return (x != y) def same(self, x, y): return (self.find(x) == self.find(y)) def size(self, x): return -self.data[self.find(x)] def prime_table(n): list = [True for _ in range(n + 1)] i = 2 while i * i <= n: if list[i]: j = i + i while j <= n: list[j] = False j += i i += 1 table = [i for i in range(n + 1) if list[i] and i >= 2] return table N, P = [int(i) for i in input().split()] uf = UnionFind(N + 1) for p in prime_table(N): q = p while q <= N: uf.union(p, q) q += p print(uf.size(P))