Submission #2214615


Source Code Expand

from collections import defaultdict

N, K, L = map(int, input().split())
roads = [list(map(int, input().split())) for i in range(K)]
trains = [list(map(int, input().split())) for i in range(L)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)

    # 検索
    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
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p-1, q-1)

for r, s in trains:
    train_uf.union(r-1, s-1)

road_par = road_uf.par
train_par = train_uf.par

ans = []
d = defaultdict(int)
for i in range(N):
    d[road_par[i], train_par[i]] += 1
ans = (d[road_par[i], train_par[i]] for i in range(N))

print(' '.join(str(i) for i in ans))

Submission Info

Submission Time
Task D - Connectivity
User AT274
Language Python (3.4.3)
Score 0
Code Size 1321 Byte
Status WA
Exec Time 1312 ms
Memory 102744 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 21 ms 3316 KB
subtask1_0.txt AC 923 ms 46092 KB
subtask1_1.txt WA 1312 ms 102744 KB
subtask1_10.txt AC 954 ms 48284 KB
subtask1_11.txt WA 1249 ms 91708 KB
subtask1_12.txt WA 1198 ms 87500 KB
subtask1_13.txt WA 1173 ms 91156 KB
subtask1_14.txt WA 1190 ms 89632 KB
subtask1_2.txt WA 1087 ms 77288 KB
subtask1_3.txt WA 1196 ms 93204 KB
subtask1_4.txt WA 1191 ms 90544 KB
subtask1_5.txt AC 979 ms 49024 KB
subtask1_6.txt WA 1195 ms 87592 KB
subtask1_7.txt WA 1233 ms 89296 KB
subtask1_8.txt WA 1228 ms 95860 KB
subtask1_9.txt WA 1156 ms 84144 KB