結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー sk4rd
提出日時 2024-06-07 23:28:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,351 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 289,152 KB
最終ジャッジ日時 2024-12-27 14:35:51
合計ジャッジ時間 41,252 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25 WA * 4 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

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