結果
問題 | No.1955 Not Prime |
ユーザー | terasa |
提出日時 | 2022-05-23 00:53:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 3,420 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 81,836 KB |
実行使用メモリ | 204,804 KB |
最終ジャッジ日時 | 2023-10-20 17:24:35 |
合計ジャッジ時間 | 5,640 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 113 ms
94,640 KB |
testcase_01 | AC | 112 ms
94,640 KB |
testcase_02 | AC | 116 ms
94,640 KB |
testcase_03 | AC | 115 ms
94,640 KB |
testcase_04 | AC | 113 ms
94,640 KB |
testcase_05 | AC | 114 ms
94,640 KB |
testcase_06 | AC | 143 ms
101,312 KB |
testcase_07 | AC | 210 ms
101,584 KB |
testcase_08 | AC | 201 ms
101,584 KB |
testcase_09 | AC | 205 ms
101,524 KB |
testcase_10 | AC | 141 ms
101,372 KB |
testcase_11 | AC | 342 ms
204,804 KB |
testcase_12 | AC | 170 ms
101,584 KB |
testcase_13 | AC | 203 ms
101,524 KB |
testcase_14 | AC | 145 ms
101,484 KB |
testcase_15 | AC | 147 ms
101,484 KB |
testcase_16 | AC | 160 ms
101,468 KB |
testcase_17 | AC | 174 ms
101,484 KB |
testcase_18 | AC | 204 ms
101,524 KB |
testcase_19 | AC | 275 ms
101,524 KB |
testcase_20 | AC | 113 ms
94,648 KB |
testcase_21 | AC | 179 ms
101,584 KB |
testcase_22 | AC | 112 ms
94,644 KB |
testcase_23 | AC | 113 ms
94,644 KB |
testcase_24 | AC | 114 ms
94,648 KB |
testcase_25 | AC | 111 ms
94,644 KB |
ソースコード
import sys import pypyjit import itertools import heapq import math from collections import deque, defaultdict, Counter import string import random input = sys.stdin.readline sys.setrecursionlimit(10 ** 6) pypyjit.set_param('max_unroll_recursion=-1') class PrimeTable: def __init__(self, N): self.is_prime = [True] * (N + 1) self.is_prime[0] = False self.is_prime[1] = False for i in range(2, N + 1): if i * i > N: break if self.is_prime[i] is False: continue for j in range(2, N + 1): if i * j > N: break self.is_prime[i * j] = False self.primes = [n for n in range(2, N + 1) if self.is_prime[n]] def is_prime(self, n): return self.is_prime[n] class SCC: def __init__(self, N, E, I): self.N = N self.E = E self.I = I self.V = [] self.C = [] self.traverse() self.traverse2() def toDAG(self): cidx = [None] * self.N for i in range(len(self.C)): for v in self.C[i]: cidx[v] = i edge = [set() for _ in range(len(self.C))] for v in range(self.N): cv = cidx[v] for dest in self.E[v]: cdest = cidx[dest] if cv == cdest: continue edge[cv].add(cdest) edge = [list(s) for s in edge] return self.C, edge def traverse(self): flag = [False] * self.N for i in range(self.N): if flag[i] is False: self.dfs(i, flag) self.V.reverse() def traverse2(self): flag = [False] * self.N for v in self.V: if flag[v] is False: idx = len(self.C) self.C.append([]) self.dfs2(idx, v, flag) def dfs(self, v, flag): flag[v] = True for dest in self.E[v]: if flag[dest] is False: self.dfs(dest, flag) self.V.append(v) def dfs2(self, idx, v, flag): flag[v] = True self.C[idx].append(v) for dest in self.I[v]: if flag[dest] is False: self.dfs2(idx, dest, flag) primes = set(PrimeTable(10 ** 6).primes) N = int(input()) idx = defaultdict(list) E = [[] for _ in range(4 * N)] I = [[] for _ in range(4 * N)] for i in range(N): a, b = map(int, input().split()) u, v = 2 * i, 2 * i + 1 idx[a].append(u) idx[b].append(v) us, ut = 2 * u, 2 * u + 1 vs, vt = 2 * v, 2 * v + 1 E[us].append(vt) E[vt].append(us) E[ut].append(vs) E[vs].append(ut) I[us].append(vt) I[vt].append(us) I[ut].append(vs) I[vs].append(ut) for s in idx.keys(): for t in idx.keys(): n = int(str(s) + str(t)) if n in primes: for i in idx[s]: for j in idx[t]: if i == j: continue us, ut = 2 * i, 2 * i + 1 vs, vt = 2 * j, 2 * j + 1 E[us].append(vs) E[vt].append(ut) I[vs].append(us) I[ut].append(vt) scc = SCC(4 * N, E, I).C for vs in scc: vvs = [v // 2 for v in vs] if len(set(vvs)) < len(vs): print('No') exit() print('Yes')