結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー flippergo
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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")
0