結果

問題 No.2780 The Bottle Imp
ユーザー lydialitvyaklydialitvyak
提出日時 2024-06-09 10:28:20
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 2,570 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 93,092 KB
最終ジャッジ日時 2024-06-09 10:28:29
合計ジャッジ時間 7,335 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
10,880 KB
testcase_01 AC 28 ms
10,880 KB
testcase_02 AC 27 ms
10,880 KB
testcase_03 AC 27 ms
10,880 KB
testcase_04 AC 29 ms
10,880 KB
testcase_05 AC 27 ms
11,008 KB
testcase_06 AC 26 ms
11,008 KB
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 AC 609 ms
93,084 KB
testcase_13 AC 639 ms
93,092 KB
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 AC 165 ms
27,620 KB
testcase_28 AC 164 ms
27,628 KB
testcase_29 RE -
testcase_30 AC 197 ms
45,100 KB
testcase_31 AC 342 ms
53,656 KB
testcase_32 AC 81 ms
13,036 KB
testcase_33 RE -
testcase_34 RE -
testcase_35 AC 76 ms
14,136 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 74 ms
14,264 KB
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 AC 26 ms
11,008 KB
testcase_43 AC 26 ms
11,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict


def parse_input():
    import sys

    input = sys.stdin.read
    lines = input().strip().split("\n")
    N = int(lines[0].strip())
    connections = []
    for i in range(1, N + 1):
        parts = list(map(int, lines[i].strip().split()))
        M_i = parts[0]
        A_i = parts[1:]
        connections.append(A_i)
    return N, connections


def build_graph(N, connections):
    graph = defaultdict(list)
    for i in range(N):
        for person in connections[i]:
            graph[i + 1].append(person)
    return graph


def tarjan_scc(N, graph):
    index = 0
    stack = []
    indices = [-1] * (N + 1)
    lowlinks = [-1] * (N + 1)
    on_stack = [False] * (N + 1)
    sccs = []

    def strongconnect(v):
        nonlocal index
        indices[v] = lowlinks[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        for w in graph[v]:
            if indices[w] == -1:
                strongconnect(w)
                lowlinks[v] = min(lowlinks[v], lowlinks[w])
            elif on_stack[w]:
                lowlinks[v] = min(lowlinks[v], indices[w])

        if lowlinks[v] == indices[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)

    for v in range(1, N + 1):
        if indices[v] == -1:
            strongconnect(v)

    return sccs


def can_pass_to_all(N, sccs, graph):
    scc_map = {}
    for i, scc in enumerate(sccs):
        for node in scc:
            scc_map[node] = i

    dag = defaultdict(set)
    for v in range(1, N + 1):
        for w in graph[v]:
            if scc_map[v] != scc_map[w]:
                dag[scc_map[v]].add(scc_map[w])

    in_degree = {i: 0 for i in range(len(sccs))}
    for u in dag:
        for v in dag[u]:
            in_degree[v] += 1

    start_scc = scc_map[1]
    if in_degree[start_scc] != 0:
        return "No"

    visited = set()
    stack = [start_scc]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbour in dag[node]:
                stack.append(neighbour)

    if len(visited) == len(sccs):
        return "Yes"
    else:
        return "No"


def main():
    N, connections = parse_input()
    graph = build_graph(N, connections)
    sccs = tarjan_scc(N, graph)
    result = can_pass_to_all(N, sccs, graph)
    print(result)


if __name__ == "__main__":
    main()
0