結果

問題 No.2780 The Bottle Imp
ユーザー shimon
提出日時 2024-06-09 21:51:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 260 ms / 2,000 ms
コード長 2,331 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 114,192 KB
最終ジャッジ日時 2024-12-31 01:41:31
合計ジャッジ時間 8,631 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def scc(N, edges):
    M = len(edges)
    start = [0] * (N + 1)
    elist = [0] * M
    for e in edges:
        start[e[0] + 1] += 1
    for i in range(1, N + 1):
        start[i] += start[i - 1]
    counter = start[:]
    for e in edges:
        elist[counter[e[0]]] = e[1]
        counter[e[0]] += 1
    visited = []
    low = [0] * N
    Ord = [-1] * N
    ids = [0] * N
    NG = [0, 0]

    def dfs(v):
        stack = [(v, -1, 0), (v, -1, 1)]
        while stack:
            v, bef, t = stack.pop()
            if t:
                if bef != -1 and Ord[v] != -1:
                    low[bef] = min(low[bef], Ord[v])
                    stack.pop()
                    continue
                low[v] = NG[0]
                Ord[v] = NG[0]
                NG[0] += 1
                visited.append(v)
                for i in range(start[v], start[v + 1]):
                    to = elist[i]
                    if Ord[to] == -1:
                        stack.append((to, v, 0))
                        stack.append((to, v, 1))
                    else:
                        low[v] = min(low[v], Ord[to])
            else:
                if low[v] == Ord[v]:
                    while (True):
                        u = visited.pop()
                        Ord[u] = N
                        ids[u] = NG[1]
                        if u == v:
                            break
                    NG[1] += 1
                low[bef] = min(low[bef], low[v])
    for i in range(N):
        if Ord[i] == -1:
            dfs(i)
    for i in range(N):
        ids[i] = NG[1] - 1 - ids[i]
    group_num = NG[1]
    counts = [0] * group_num
    for x in ids:
        counts[x] += 1
    groups = [[] for i in range(group_num)]
    for i in range(N):
        groups[ids[i]].append(i)
    return groups


N = int(input())
edges = []
for _ in range(N):
    m, *A = map(int, input().split())
    for a in A:
        edges.append((_, a - 1))

groups = scc(N, edges)
M = len(groups)
G = [[] for _ in range(M)]
d = [0] * N
for i, group in enumerate(groups):
    for x in group:
        d[x] = i
for e in edges:
    x, y = e
    if d[x] != d[y]:
        G[d[x]].append(d[y])

if 0 not in groups[0]:
    print('No')
else:
    for i in range(M - 1):
        if i + 1 not in G[i]:
            print('No')
            exit()
    print('Yes')
0