結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー flippergo
提出日時 2025-03-27 10:17:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,569 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 284,016 KB
最終ジャッジ日時 2025-03-27 10:17:18
合計ジャッジ時間 12,078 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 39 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
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])
visited = [0]*(N+1)
def dfs(v):
    visited[v] = 1
    for u in FG[v]:
        if visited[u]==0:
            dfs(u)
dfs(1)
flag = True
for i in range(1,N+1):
    if visited[i]==0:
        flag = False
        break
if not flag:
    print("No")
else:
    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
    dfs1(1) 
    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:[] 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].append(col[j])
    inDeg = [0]*cnt
    outDeg = [0]*cnt
    for c in G:
        for d in G[c]:
            inDeg[d] += 1
            outDeg[c] += 1
    inmax = max(inDeg)
    outmax = max(outDeg)
    if inmax<=1 and outmax<=1:
        print("Yes")
    else:
        print("No")
0