結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
from collections import Counter, defaultdict, dequeimport sysinput=sys.stdin.readlineN=int(input())n=N#n,m=map(int,input().split())class SCC:def __init__(self,n):self.n = nself.edges = []def add_edge(self,a,b):self.edges.append((a,b))def scc(self):n = self.ncounter = [0]*(n+1)elist = [0]*len(self.edges)for x,y in self.edges:counter[x+1] += 1for x in range(n):counter[x+1] += counter[x]start = counter[:]for x,y in self.edges:elist[counter[x]] = ycounter[x] += 1k = 0low = [0]*nnum = [-1]*npre = [None]*nvisited = []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] = kk += 1visited.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] = xelse:low[x] = min(low[x],num[y])else:if low[x] == num[x]:scc = []while 1:y = visited.pop()num[y] = nscc.append(y)if x == y:breaksccs.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]*Ns=0for i in range(len(ans)):B=ans[i]for b in B:D[b]=iif b==0:s=iDD={}for x,y in C:x,y=D[x],D[y]if x==y:continueif x not in DD:DD[x]=[y]V=[-1]*dfrom collections import dequed=deque()d.append(s)while d:now=d.popleft()V[now]=1if now in DD:nex=DD[now][0]if V[nex]==-1:d.append(nex)if len(set(V))==1:print('Yes')else:print('No')