結果
問題 | No.1955 Not Prime |
ユーザー | roaris |
提出日時 | 2022-05-27 22:52:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 2,328 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 81,848 KB |
実行使用メモリ | 110,468 KB |
最終ジャッジ日時 | 2023-10-20 20:35:23 |
合計ジャッジ時間 | 5,670 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
67,104 KB |
testcase_01 | AC | 73 ms
67,104 KB |
testcase_02 | AC | 71 ms
67,104 KB |
testcase_03 | AC | 75 ms
67,104 KB |
testcase_04 | AC | 71 ms
67,104 KB |
testcase_05 | AC | 71 ms
67,104 KB |
testcase_06 | AC | 141 ms
84,064 KB |
testcase_07 | AC | 336 ms
88,368 KB |
testcase_08 | AC | 310 ms
86,960 KB |
testcase_09 | AC | 279 ms
87,256 KB |
testcase_10 | AC | 93 ms
78,688 KB |
testcase_11 | AC | 198 ms
110,468 KB |
testcase_12 | AC | 226 ms
85,788 KB |
testcase_13 | AC | 331 ms
87,560 KB |
testcase_14 | AC | 251 ms
86,228 KB |
testcase_15 | AC | 237 ms
86,304 KB |
testcase_16 | AC | 293 ms
86,520 KB |
testcase_17 | AC | 346 ms
90,532 KB |
testcase_18 | AC | 311 ms
86,696 KB |
testcase_19 | AC | 224 ms
86,836 KB |
testcase_20 | AC | 72 ms
67,108 KB |
testcase_21 | AC | 221 ms
85,992 KB |
testcase_22 | AC | 72 ms
67,104 KB |
testcase_23 | AC | 71 ms
67,104 KB |
testcase_24 | AC | 71 ms
67,104 KB |
testcase_25 | AC | 71 ms
67,104 KB |
ソースコード
import sys input = sys.stdin.readline sys.setrecursionlimit(1010) def era(n): is_prime = [True]*(n+1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n**0.5)+1): if not is_prime[i]: continue for j in range(2*i, n+1, i): is_prime[j] = False return is_prime class Scc: def __init__(self, N, G): self.N = N self.G = G self.RG = [[] for _ in range(N)] for v in range(N): for nv in G[v]: self.RG[nv].append(v) def decomp(self): order = [] visited = [False]*self.N def dfs(v): visited[v] = True for nv in self.G[v]: if not visited[nv]: dfs(nv) order.append(v) for v in range(self.N): if not visited[v]: dfs(v) visited = [False]*self.N comp = [-1]*self.N label = 0 def rdfs(v, label): comp[v] = label visited[v] = True for nv in self.RG[v]: if not visited[nv]: rdfs(nv, label) for v in reversed(order): if not visited[v]: rdfs(v, label) label += 1 return label, comp def is_p(p, q): return is_prime[p*pow(10, len(str(q)))+q] N = int(input()) AB = [tuple(map(int, input().split())) for _ in range(N)] is_prime = era(10**6+10) G = [[] for _ in range(2*N)] for i in range(N): Ai, Bi = AB[i] for j in range(i, N): Aj, Bj = AB[j] if is_p(Ai, Bj) or is_p(Aj, Bi): G[2*i+1].append(2*j) G[2*j+1].append(2*i) if is_p(Bi, Bj) or is_p(Aj, Ai): G[2*i].append(2*j) G[2*j+1].append(2*i+1) if is_p(Ai, Aj) or is_p(Bj, Bi): G[2*i+1].append(2*j+1) G[2*j].append(2*i) if is_p(Bi, Aj) or is_p(Bj, Ai): G[2*i].append(2*j+1) G[2*j].append(2*i+1) scc = Scc(2*N, G) _, comp = scc.decomp() for i in range(N): if comp[2*i]==comp[2*i+1]: exit(print('No')) print('Yes')