結果

問題 No.1955 Not Prime
ユーザー lam6er
提出日時 2025-04-09 21:04:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 435 ms / 2,000 ms
コード長 2,418 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 238,696 KB
最終ジャッジ日時 2025-04-09 21:06:16
合計ジャッジ時間 5,091 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    max_prime = 10**6
    sieve = [True] * (max_prime + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(max_prime**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, max_prime + 1, i):
                sieve[j] = False

    N = int(sys.stdin.readline())
    pairs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    size = 2 * N
    adj = [[] for _ in range(2 * N * 2)]

    for i in range(N):
        a_i, b_i = pairs[i]
        for j in range(N):
            a_j, b_j = pairs[j]
            for x in [0, 1]:
                s = a_i if x == 0 else b_i
                for y in [0, 1]:
                    t = b_j if y == 0 else a_j
                    concat = int(f"{s}{t}")
                    if concat > max_prime:
                        is_p = False
                    else:
                        is_p = sieve[concat]
                    if is_p:
                        xi_node = 2 * i + (1 if x == 0 else 0)
                        not_yj_node = 2 * j + (0 if y == 0 else 1)
                        adj[xi_node].append(not_yj_node)
                        yj_node = 2 * j + (1 if y == 0 else 0)
                        not_xi_node = 2 * i + (0 if x == 0 else 1)
                        adj[yj_node].append(not_xi_node)

    visited = [False] * (2 * N)
    order = []
    def dfs(u):
        if visited[u]:
            return
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
        order.append(u)

    for u in range(2 * N):
        if not visited[u]:
            dfs(u)

    visited = [False] * (2 * N)
    component = [0] * (2 * N)
    current = 0

    def reverse_dfs(u, current):
        stack = [u]
        while stack:
            node = stack.pop()
            if visited[node]:
                continue
            visited[node] = True
            component[node] = current
            for v in adj[node ^ 1]:
                if not visited[v ^ 1]:
                    stack.append(v ^ 1)

    order.reverse()
    for u in order:
        if not visited[u]:
            reverse_dfs(u, current)
            current += 1

    possible = True
    for i in range(N):
        if component[2 * i] == component[2 * i + 1]:
            possible = False
            break

    print("Yes" if possible else "No")

if __name__ == "__main__":
    main()
0