結果

問題 No.2780 The Bottle Imp
ユーザー timitimi
提出日時 2024-06-07 23:04:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 257 ms / 2,000 ms
コード長 2,626 bytes
コンパイル時間 515 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 121,008 KB
最終ジャッジ日時 2024-12-27 14:29:17
合計ジャッジ時間 7,630 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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

from collections import Counter, defaultdict, deque
import sys
input=sys.stdin.readline
N=int(input())
n=N
#n,m=map(int,input().split())
class SCC:
def __init__(self,n):
self.n = n
self.edges = []
def add_edge(self,a,b):
self.edges.append((a,b))
def scc(self):
n = self.n
counter = [0]*(n+1)
elist = [0]*len(self.edges)
for x,y in self.edges:
counter[x+1] += 1
for x in range(n):
counter[x+1] += counter[x]
start = counter[:]
for x,y in self.edges:
elist[counter[x]] = y
counter[x] += 1
k = 0
low = [0]*n
num = [-1]*n
pre = [None]*n
visited = []
q = []
sccs = []
for x in range(n):
if num[x] < 0:
q.append(x)
q.append(x)
while q:
x = q.pop()
if num[x] < 0:
low[x] = num[x] = k
k += 1
visited.append(x)
for i in range(start[x],start[x+1]):
y = elist[i]
if num[y] < 0:
q.append(y)
q.append(y)
pre[y] = x
else:
low[x] = min(low[x],num[y])
else:
if low[x] == num[x]:
scc = []
while 1:
y = visited.pop()
num[y] = n
scc.append(y)
if x == y:
break
sccs.append(scc)
y = pre[x]
if y is not None:
low[y] = min(low[y],low[x])
return sccs[::-1]
scc = SCC(n)
C=[]
for i in range(N):
A=list(map(int, input().split()))
B=A[1:]
for b in B:
C.append((i,b-1))
scc.add_edge(i,b-1)
ans = scc.scc()
d=len(ans)
D=[-1]*N
s=0
for i in range(len(ans)):
B=ans[i]
for b in B:
D[b]=i
if b==0:
s=i
DD={}
for x,y in C:
x,y=D[x],D[y]
if x==y:
continue
if x not in DD:
DD[x]=[y]
V=[-1]*d
from collections import deque
d=deque()
d.append(s)
while d:
now=d.popleft()
V[now]=1
if now in DD:
nex=DD[now][0]
if V[nex]==-1:
d.append(nex)
if len(set(V))==1:
print('Yes')
else:
print('No')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0