結果

問題 No.3508 OR Mapping
コンテスト
ユーザー Shiny
提出日時 2026-04-18 01:26:04
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 3,120 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 697 ms
コンパイル使用メモリ 20,656 KB
実行使用メモリ 271,964 KB
最終ジャッジ日時 2026-04-18 01:27:15
合計ジャッジ時間 14,899 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 7 TLE * 2 -- * 56
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque
from math import gcd

sys.setrecursionlimit(1_000_000)
input = sys.stdin.readline

n, m, k = map(int, input().split())
graph = [[] for _ in range(n)]
rev_graph = [[] for _ in range(n)]
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    rev_graph[v].append(u)
    edges.append((u, v))

used = [0] * n
order = []
for start in range(n):
    if used[start]:
        continue
    used[start] = 1
    stack = [[start, 0]]
    while stack:
        node, idx = stack[-1]
        if idx < len(graph[node]):
            nxt = graph[node][idx]
            stack[-1][1] += 1
            if not used[nxt]:
                used[nxt] = 1
                stack.append([nxt, 0])
        else:
            order.append(node)
            stack.pop()

comp = [-1] * n
groups = []
for start in reversed(order):
    if comp[start] != -1:
        continue
    cid = len(groups)
    groups.append([])
    stack = [start]
    comp[start] = cid
    while stack:
        node = stack.pop()
        groups[cid].append(node)
        for prv in rev_graph[node]:
            if comp[prv] == -1:
                comp[prv] = cid
                stack.append(prv)

scc_count = len(groups)
start_scc = comp[0]
size = [len(vs) for vs in groups]
is_single = [len(vs) == 1 for vs in groups]

if is_single[start_scc]:
    print("No")
    raise SystemExit

depth = [-1] * n
for cid, vertices in enumerate(groups):
    if is_single[cid]:
        continue

    for v in vertices:
        depth[v] = -1

    root = vertices[0]
    depth[root] = 0
    stack = [root]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if comp[nxt] != cid or depth[nxt] != -1:
                continue
            depth[nxt] = depth[node] + 1
            stack.append(nxt)

    period = 0
    for v in vertices:
        for nxt in graph[v]:
            if comp[nxt] != cid:
                continue
            period = gcd(period, abs(depth[v] + 1 - depth[nxt]))

    if period % 2 == 0:
        print("No")
        raise SystemExit

# Remove edges between two singleton SCCs.
dag_edges = []
for u, v in edges:
    cu = comp[u]
    cv = comp[v]
    if cu == cv:
        continue
    if is_single[cu] and is_single[cv]:
        continue
    dag_edges.append((cu, cv))

dag_edges.sort()
filtered = []
prev = (-1, -1)
for e in dag_edges:
    if e != prev:
        filtered.append(e)
        prev = e

dag = [[] for _ in range(scc_count)]
indeg = [0] * scc_count
for a, b in filtered:
    dag[a].append(b)
    indeg[b] += 1

queue = deque(i for i in range(scc_count) if indeg[i] == 0)
topo = []
while queue:
    node = queue.popleft()
    topo.append(node)
    for nxt in dag[node]:
        indeg[nxt] -= 1
        if indeg[nxt] == 0:
            queue.append(nxt)

NEG = -10**9
best = [NEG] * scc_count
best[start_scc] = 1
for node in topo:
    if best[node] < 0:
        continue
    base = best[node] + 1
    for nxt in dag[node]:
        if best[nxt] < base:
            best[nxt] = base

print("Yes" if max(best) == scc_count else "No")
0