結果
問題 |
No.2780 The Bottle Imp
|
ユーザー |
![]() |
提出日時 | 2024-06-07 22:39:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 426 ms / 2,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 118,008 KB |
最終ジャッジ日時 | 2024-12-27 14:15:31 |
合計ジャッジ時間 | 10,208 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
n=int(input()) e=[[] for i in range(n)] re=[[] for i in range(n)] for i in range(n): m,*t,=map(int,input().split()) for j in range(m): e[i]+=[t[j]-1] re[t[j]-1]+=[i] v=[0]*n g=[0]*n o=[] for i in range(n): if v[i]==0: q=[i] while len(q)>0: s=q[-1] v[s]=1 while g[s]<len(e[s]): t=e[s][g[s]] if v[t]==0: break g[s]+=1 if g[s]<len(e[s]): q+=[t] else: o+=[s] q.pop() v=[0]*n g=[0]*n p=[0]*n c=0 for i in o[::-1]: if v[i]==0: s=i v[s]=1 q=[s] for s in q: p[s]=c for t in re[s]: if v[t]==0: v[t]=1 q+=[t] c+=1 E=[[] for i in range(c)] d=[0]*c for s in range(n): for t in e[s]: if p[s]!=p[t]: E[p[s]]+=[p[t]] d[p[t]]+=1 r=[] q=[i for i in range(c) if d[i]==0] for s in q: r+=[s] for t in E[s]: d[t]-=1 if d[t]==0: q+=[t] f=r[0]==p[0] for i in range(c-1): f&=r[i+1] in E[r[i]] print(["No","Yes"][f])