結果

問題 No.2780 The Bottle Imp
ユーザー shimonohnishishimonohnishi
提出日時 2024-06-09 21:51:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 2,331 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 114,452 KB
最終ジャッジ日時 2024-06-09 21:51:59
合計ジャッジ時間 8,643 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,816 KB
testcase_01 AC 41 ms
54,056 KB
testcase_02 AC 40 ms
53,308 KB
testcase_03 AC 38 ms
53,792 KB
testcase_04 AC 39 ms
54,384 KB
testcase_05 AC 40 ms
53,684 KB
testcase_06 AC 37 ms
52,888 KB
testcase_07 AC 221 ms
85,252 KB
testcase_08 AC 246 ms
91,272 KB
testcase_09 AC 194 ms
86,560 KB
testcase_10 AC 205 ms
87,076 KB
testcase_11 AC 197 ms
84,824 KB
testcase_12 AC 245 ms
100,376 KB
testcase_13 AC 274 ms
105,156 KB
testcase_14 AC 117 ms
88,796 KB
testcase_15 AC 120 ms
88,772 KB
testcase_16 AC 117 ms
88,780 KB
testcase_17 AC 119 ms
88,664 KB
testcase_18 AC 116 ms
88,788 KB
testcase_19 AC 113 ms
88,796 KB
testcase_20 AC 119 ms
88,672 KB
testcase_21 AC 117 ms
88,520 KB
testcase_22 AC 184 ms
81,228 KB
testcase_23 AC 117 ms
84,984 KB
testcase_24 AC 193 ms
88,040 KB
testcase_25 AC 210 ms
89,384 KB
testcase_26 AC 178 ms
89,620 KB
testcase_27 AC 123 ms
90,424 KB
testcase_28 AC 124 ms
90,580 KB
testcase_29 AC 163 ms
85,972 KB
testcase_30 AC 126 ms
82,508 KB
testcase_31 AC 160 ms
86,576 KB
testcase_32 AC 87 ms
88,056 KB
testcase_33 AC 183 ms
108,816 KB
testcase_34 AC 188 ms
114,452 KB
testcase_35 AC 84 ms
80,768 KB
testcase_36 AC 33 ms
52,712 KB
testcase_37 AC 33 ms
53,140 KB
testcase_38 AC 88 ms
80,904 KB
testcase_39 AC 180 ms
97,664 KB
testcase_40 AC 158 ms
97,492 KB
testcase_41 AC 157 ms
97,552 KB
testcase_42 AC 33 ms
52,716 KB
testcase_43 AC 33 ms
54,592 KB
権限があれば一括ダウンロードができます

ソースコード

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