結果
| 問題 | No.3508 OR Mapping |
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2026-04-18 14:17:48 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 1,089 ms / 2,000 ms |
| コード長 | 4,394 bytes |
| 記録 | |
| コンパイル時間 | 170 ms |
| コンパイル使用メモリ | 85,504 KB |
| 実行使用メモリ | 306,460 KB |
| 最終ジャッジ日時 | 2026-04-18 14:18:22 |
| 合計ジャッジ時間 | 28,529 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 65 |
ソースコード
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()
a = [0] * n
for t in range(len(res)):
for i in res[t]:
a[i] = t
dist = [-1] * n
q = []
f = [0] * len(res)
for i in range(n):
if f[a[i]] == 0:
f[a[i]] = 1
q.append(i)
dist[i] = 0
while q:
x = q.pop()
for y in g[x]:
if dist[y] == -1 and a[x] == a[y]:
dist[y] = dist[x] + 1
q.append(y)
ans = [0] * len(res)
for i in range(n):
for j in g[i]:
if a[i] == a[j]:
ans[a[i]] = gcd(ans[a[i]], dist[j] - dist[i] - 1)
# print(ans)
ok = [0] * (len(res) - 1)
for i in range(n):
for j in g[i]:
if a[j] == a[i] + 1:
ok[a[i]] = 1
if 0 in res[0] and all(x == 1 for x in ok) and all(x == 0 or x % 2 == 1 for x in ans) and all(ans[i] != 0 or ans[i+1] != 0 for i in range(len(ans) - 1)) and ans[0] != 0:
Yes()
else:
No()
solve()