結果

問題 No.2780 The Bottle Imp
ユーザー sk4rdsk4rd
提出日時 2024-06-07 23:28:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,351 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 101,404 KB
最終ジャッジ日時 2024-06-08 10:38:24
合計ジャッジ時間 4,513 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
62,332 KB
testcase_01 AC 44 ms
55,572 KB
testcase_02 AC 44 ms
55,912 KB
testcase_03 AC 43 ms
55,312 KB
testcase_04 AC 44 ms
54,652 KB
testcase_05 AC 43 ms
55,944 KB
testcase_06 AC 42 ms
54,932 KB
testcase_07 AC 180 ms
83,104 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque
from itertools import product
INF = int(1e18); arr4 = ((-1, 0), (0, -1), (1, 0), (0, 1))
def dmp(*args, sep=" ", end="\n"): print(*args, sep=sep, end=end, file=sys.stderr)
if "DEBUG" not in sys.argv: dmp = lambda *args: None
import pypyjit
sys.setrecursionlimit(10**7); pypyjit.set_param('max_unroll_recursion=0')

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0: return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    def merge(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.size(x) < self.size(y): x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.parents[self.find(x)]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def groups(self):
        res = [set() for _ in range(self.n)]
        for i in range(self.n):
            res[self.find(i)].add(i)
        res = [x for x in res if len(x) > 0]
        return res
    def __str__(self):
        return ' '.join([str(x) for x in self.groups()])


n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
    m, *a = map(lambda x: int(x)-1, input().split())
    for x in a:
        graph[i].append(x)
visited = [0] * n
r = [0] * n

uf = UnionFind(n)

def dfs(v, l):
    visited[v] = 1
    r[v] = 1
    res = -1
    for nv in graph[v]:
        if not visited[nv]:  res = dfs(nv, l+1)
        elif r[nv]:
            uf.merge(v, nv)
            res = nv
    r[v] = 0
    if res > -1: uf.merge(v, res)
    return res


dfs(0, 0)
leng = [0] * n
visited = defaultdict(int)

def dfs2(fv, l):
    g = uf.group(fv)
    visited[fv] = 1
    l += len(g)
    nxts = set()
    for v in g:
        leng[v] = l
        for nv in graph[v]:
            nxts.add(uf.find(nv))
    for nf in nxts:
        if not visited[uf.find(nf)]: dfs2(nf, l)
    
dfs2(uf.find(0), 0)
print('Yes' if max(leng) == n else 'No')
0