結果
問題 |
No.2780 The Bottle Imp
|
ユーザー |
|
提出日時 | 2025-03-27 12:11:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 568 ms / 2,000 ms |
コード長 | 1,484 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 251,548 KB |
最終ジャッジ日時 | 2025-03-27 12:12:08 |
合計ジャッジ時間 | 13,153 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import sys from collections import deque sys.setrecursionlimit(10**6) N = int(input()) FG = {i:[] for i in range(1,N+1)} for i in range(1,N+1): A = list(map(int,input().split())) for j in range(1,A[0]+1): FG[i].append(A[j]) A = [0]*(N+1) invA = [0]*(N+1) visited = [0]*(N+1) cnt = 1 def dfs1(v): global cnt visited[v] = 1 for u in FG[v]: if visited[u]==0: dfs1(u) A[v] = cnt invA[cnt] = v cnt += 1 for i in range(1,N+1): if visited[i]==0: dfs1(i) BG = {i:[] for i in range(1,N+1)} for i in range(1,N+1): for j in FG[i]: BG[j].append(i) Col = [0]*(N+1) cnt = 1 def dfs2(v,cnt): Col[v] = cnt for u in BG[v]: if Col[u]==0: dfs2(u,cnt) for i in range(N,0,-1): if Col[invA[i]]==0: dfs2(invA[i],cnt) cnt += 1 G = {c:set([]) for c in range(1,cnt)} for i in range(1,N+1): c = Col[i] for j in FG[i]: if Col[j]!=c: G[c].add(Col[j]) inDeg = [0]*cnt outDeg = [0]*cnt for c in G: outDeg[c] = len(G[c]) for d in G[c]: inDeg[d] += 1 c1 = Col[1] if inDeg[c1]==0 and inDeg[1:].count(0)==1 and outDeg[1:].count(0)==1: flag = "Yes" que = deque([c1]) while que: c = que.popleft() for d in G[c]: inDeg[d] -= 1 if inDeg[d]==0: que.append(d) if len(que)>1: flag = "No" break print(flag) else: print("No")