Submission #2214578
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+1)] 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 x == y: pass elif 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, q) for r, s in trains: train_uf.union(r, s) road_par = road_uf.par train_par = train_uf.par ans = [] d = defaultdict(int) for i in range(1, N+1): d[road_par[i], train_par[i]] += 1 ans = (d[road_par[i], train_par[i]] for i in range(1, N+1)) 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 | 1365 Byte |
Status | WA |
Exec Time | 1235 ms |
Memory | 102488 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
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 | 20 ms | 3316 KB |
subtask0_1.txt | AC | 20 ms | 3316 KB |
subtask0_2.txt | AC | 20 ms | 3316 KB |
subtask1_0.txt | AC | 826 ms | 46092 KB |
subtask1_1.txt | WA | 1195 ms | 102488 KB |
subtask1_10.txt | AC | 880 ms | 48284 KB |
subtask1_11.txt | WA | 1158 ms | 91580 KB |
subtask1_12.txt | WA | 1159 ms | 87500 KB |
subtask1_13.txt | WA | 1156 ms | 91156 KB |
subtask1_14.txt | WA | 1196 ms | 89636 KB |
subtask1_2.txt | WA | 1049 ms | 77288 KB |
subtask1_3.txt | WA | 1211 ms | 93204 KB |
subtask1_4.txt | WA | 1203 ms | 90544 KB |
subtask1_5.txt | AC | 858 ms | 49024 KB |
subtask1_6.txt | WA | 1104 ms | 87464 KB |
subtask1_7.txt | WA | 1133 ms | 89168 KB |
subtask1_8.txt | WA | 1235 ms | 95860 KB |
subtask1_9.txt | WA | 1134 ms | 84140 KB |