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 |
|
|
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 |