Submission #4046557


Source Code Expand

import collections
N,K,L = map(int, input().split())
p = []
q = []
for i in range(K):#h:高さ
    pi, qi = map(int, input().split())
    p.append(pi)
    q.append(qi)
r = []
s = []
for i in range(L):#h:高さ
    ri, si = map(int, input().split())
    r.append(ri)
    s.append(si)

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する(初期状態では0)
        self.rank = [0] * (n + 1)

    # 検索
    # 根ならその番号を返す
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

        # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(N)
for i in range(K):
    u.union(p[i],q[i])


u2 = UnionFind(N)
for i in range(L):
    u2.union(r[i],s[i])

li = [None]*(N)
liw = [None]*(N)
for i in range(N):
    li[i] = (u.par[i + 1], u2.par[i + 1], i + 1)
    liw[i] = (u.par[i + 1], u2.par[i + 1])
#li.sort(key=lambda x:(x[0], x[1]))

liws = collections.Counter(liw)

ansli = [0]*(N+1)
for i in range(N):
    ansli[i + 1] = liws[(li[i][0], li[i][1])]

for i in range(1, N + 1):
    print(ansli[i], "", end="")

Submission Info

Submission Time
Task D - Connectivity
User yosho
Language Python (3.4.3)
Score 0
Code Size 1953 Byte
Status WA
Exec Time 1570 ms
Memory 87920 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
WA × 12
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 21 ms 3316 KB
subtask0_1.txt AC 21 ms 3316 KB
subtask0_2.txt AC 20 ms 3316 KB
subtask1_0.txt AC 846 ms 17320 KB
subtask1_1.txt WA 1570 ms 87920 KB
subtask1_10.txt AC 875 ms 18180 KB
subtask1_11.txt WA 1456 ms 72684 KB
subtask1_12.txt WA 1404 ms 66856 KB
subtask1_13.txt WA 1403 ms 72876 KB
subtask1_14.txt WA 1398 ms 64880 KB
subtask1_2.txt WA 1219 ms 56420 KB
subtask1_3.txt WA 1446 ms 73360 KB
subtask1_4.txt WA 1364 ms 66848 KB
subtask1_5.txt AC 882 ms 18564 KB
subtask1_6.txt WA 1388 ms 69304 KB
subtask1_7.txt WA 1377 ms 70188 KB
subtask1_8.txt WA 1499 ms 74652 KB
subtask1_9.txt WA 1314 ms 58396 KB