結果

問題 No.1955 Not Prime
ユーザー terasaterasa
提出日時 2022-05-23 00:53:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 334 ms / 2,000 ms
コード長 3,420 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 203,352 KB
最終ジャッジ日時 2024-09-20 13:00:04
合計ジャッジ時間 5,282 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
95,104 KB
testcase_01 AC 112 ms
94,464 KB
testcase_02 AC 114 ms
94,720 KB
testcase_03 AC 118 ms
94,976 KB
testcase_04 AC 113 ms
94,848 KB
testcase_05 AC 114 ms
94,976 KB
testcase_06 AC 145 ms
102,016 KB
testcase_07 AC 197 ms
102,272 KB
testcase_08 AC 195 ms
102,272 KB
testcase_09 AC 202 ms
102,272 KB
testcase_10 AC 142 ms
102,016 KB
testcase_11 AC 334 ms
203,352 KB
testcase_12 AC 164 ms
102,016 KB
testcase_13 AC 194 ms
102,272 KB
testcase_14 AC 143 ms
102,016 KB
testcase_15 AC 145 ms
102,144 KB
testcase_16 AC 156 ms
101,888 KB
testcase_17 AC 171 ms
102,144 KB
testcase_18 AC 204 ms
102,400 KB
testcase_19 AC 257 ms
102,528 KB
testcase_20 AC 113 ms
95,232 KB
testcase_21 AC 174 ms
102,272 KB
testcase_22 AC 111 ms
94,976 KB
testcase_23 AC 111 ms
94,976 KB
testcase_24 AC 110 ms
94,592 KB
testcase_25 AC 109 ms
94,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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')
0