結果

問題 No.2780 The Bottle Imp
ユーザー rlangevinrlangevin
提出日時 2024-06-07 21:53:28
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,563 bytes
コンパイル時間 1,275 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 140,256 KB
最終ジャッジ日時 2024-12-27 13:43:39
合計ジャッジ時間 8,973 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 39 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class DirectedGraph():
def __init__(self, N):
self.N = N
self.G = [[] for i in range(N)]
self.rG = [[] for i in range(N)]
self.order = []
self.used1 = [0] * N
self.used2 = [0] * N
self.group = [-1] * N
self.label = 0
self.seen = [0] * N
self.Edge = set()
def add_edge(self, u, v):
#
if (u, v) not in self.Edge:
self.G[u].append(v)
self.rG[v].append(u)
self.Edge.add((u, v))
def dfs(self, s):
stack = [~s, s]
while stack:
u = stack.pop()
if u >= 0:
if self.used1[u]:
continue
self.used1[u] = 1
for v in self.G[u]:
if self.used1[v]:
continue
stack.append(~v)
stack.append(v)
else:
u = ~u
if self.seen[u]:
continue
self.seen[u]= 1
self.order.append(u)
def rdfs(self, s, num):
stack = [s]
while stack:
u = stack.pop()
if u >= 0:
self.used2[u] = 1
self.group[u] = num
for v in self.rG[u]:
if self.used2[v]:
continue
stack.append(v)
def scc(self):
for i in range(self.N):
if self.used1[i]:
continue
if i != 0:
print("No")
exit()
self.dfs(i)
for s in reversed(self.order):
if self.used2[s]:
continue
self.rdfs(s, self.label)
self.label += 1
return self.label, self.group
def construct(self):
nG = [set() for _ in range(self.label)]
mem = [[] for i in range(self.label)]
for s in range(self.N):
now = self.group[s]
for u in self.G[s]:
if now == self.group[u]:
continue
nG[now].add(self.group[u])
mem[now].append(s)
return nG, mem
N = int(input())
G = DirectedGraph(N)
for i in range(N):
A = list(map(int, input().split()))
M = A.pop(0)
for j in range(M):
G.add_edge(i, A[j]-1)
G.scc()
nG, mem = G.construct()
if 0 not in mem[0]:
print("No")
exit()
for v in nG:
if len(v) >= 2:
print("No")
exit()
print("Yes")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0