#1159596 (PyPy3) No.3508 OR Mapping

• 問題: No.3508 OR Mapping
• ユーザー: tassei903
• 提出日時: 2026-04-18 14:05:34
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 3,935 bytes
• コンパイル時間: 279 ms
• コンパイル使用メモリ: 85,248 KB
• 実行使用メモリ: 302,960 KB
• 最終ジャッジ日時: 2026-04-18 14:06:19
• 合計ジャッジ時間: 32,870 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 47 WA * 18

ソースコード

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

# https://judge.yosupo.jp/submission/216433
# https://qiita.com/AkariLuminous/items/a2c789cebdd098dcb503
# O(N + M)
class SCC:
    def __init__(self, n):
        self.n = n
        self.edges = []
        self.start = [0] * (n + 1)
        self.mask = (1 << 31) - 1
        self.shift = 31

    def add_edge(self, a, b):
        self.edges.append((a << self.shift) + b)
        self.start[a + 1] += 1

    def csr(self):
        for i in range(self.n):
            self.start[i + 1] += self.start[i]
        counter = self.start[:]
        self.elist = [0] * len(self.edges)
        for ab in self.edges:
            a, b = ab >> self.shift, ab & self.mask
            self.elist[counter[a]] = b
            counter[a] += 1

    def scc(self):
        self.csr()
        n = self.n
        now_ord = group_num = 0 # 探索した頂点数、見つかったSCCの個数
        visited = [] # まだ確定していない頂点のリスト
        low = [0] * n # lowlink
        order = [-1] * n # order
        ids = [0] * n # scc_id
        parent = [-1] * n
        stack = []
        groups = [] # 各SCCの頂点リスト
        for i in range(n):
            if order[i] != -1:
                continue
            stack.append(i)
            stack.append(i)
            while stack:
                v = stack.pop()
                if order[v] == -1: # 1回目の訪問
                    low[v] = order[v] = now_ord
                    now_ord += 1
                    visited.append(v)
                    for k in range(self.start[v], self.start[v + 1]):
                        to = self.elist[k]
                        if order[to] == -1:
                            stack.append(to)
                            stack.append(to)
                            parent[to] = v
                        else:
                            low[v] = min(low[v], order[to])
                else: # 2回目の訪問
                    if low[v] == order[v]: # 根ならSCCが確定
                        group = []
                        while True:
                            u = visited.pop()
                            order[u] = n # 確定済み
                            ids[u] = group_num
                            group.append(u)
                            if u == v:
                                break
                        groups.append(group)
                        group_num += 1
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x
        return group_num, ids, groups[::-1]

def check(x):
    if x == 0:
        return False
    while x % 2 == 0:
        x //= 2

    while x % 5 == 0:
        x //= 5
    return x == 1

from math import gcd
def solve():
    n, m, k = na()
    scc = SCC(n)
    g = [[] for i in range(n)]
    for _ in range(m):
        a, b = na()
        a -= 1
        b -= 1
        g[a].append(b)
        scc.add_edge(a, b)
    _, _, res = scc.scc()
    if len(res) != 1:
        No()
        return
    
    z = res[0]
    a = [0] * n
    for i in z:
        a[i] = 1

    dist = [-1] * n
    q = [0]
    dist[0] = 0
    while q:
        x = q.pop()
        for y in g[x]:
            if dist[y] == -1:
                dist[y] = dist[x] + 1
                q.append(y)
    res = 0
    for i in range(n):
        if a[i]:
            for j in g[i]:
                if a[j]:
                    res = gcd(res, dist[j] - dist[i] - 1)
    
    if res % 2:
        Yes()
    else:
        No()


solve()