Submission #11232216


Source Code Expand

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
l = []
for _ in range(n):
    k, *ls = map(int, input().split())
    l.append(ls)

uf = UnionFind(m)

for li in l:
    for e1, e2 in zip(li, li[1:]):
        e1 -= 1
        e2 -= 1
        uf.unite(e1, e2)

p = uf.find_set(l[0][0] - 1)
ans = "YES"
for e, *_ in l:
    if uf.find_set(e - 1) != p:
        ans = "NO"

print(ans)

Submission Info

Submission Time
Task C - Interpretation
User shamio
Language Python (3.4.3)
Score 400
Code Size 1341 Byte
Status AC
Exec Time 444 ms
Memory 29904 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 17 ms 3064 KB
01-02.txt AC 19 ms 3188 KB
01-03.txt AC 21 ms 3188 KB
01-04.txt AC 21 ms 3188 KB
01-05.txt AC 21 ms 3188 KB
01-06.txt AC 21 ms 3188 KB
01-07.txt AC 21 ms 3188 KB
01-08.txt AC 21 ms 3188 KB
01-09.txt AC 21 ms 3188 KB
01-10.txt AC 21 ms 3316 KB
02-01.txt AC 235 ms 13232 KB
02-02.txt AC 444 ms 22972 KB
02-03.txt AC 239 ms 10996 KB
02-04.txt AC 398 ms 21880 KB
02-05.txt AC 414 ms 21076 KB
02-06.txt AC 399 ms 21908 KB
02-07.txt AC 443 ms 22876 KB
02-08.txt AC 405 ms 20980 KB
02-09.txt AC 419 ms 29904 KB
02-10.txt AC 343 ms 18696 KB
02-11.txt AC 334 ms 18724 KB
02-12.txt AC 323 ms 18264 KB
02-13.txt AC 328 ms 18232 KB
sample-01.txt AC 17 ms 3064 KB
sample-02.txt AC 17 ms 3064 KB