結果
問題 | No.1390 Get together |
ユーザー | itsy68 |
提出日時 | 2022-04-15 06:08:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 426 ms / 2,000 ms |
コード長 | 2,019 bytes |
コンパイル時間 | 1,990 ms |
コンパイル使用メモリ | 86,336 KB |
実行使用メモリ | 100,520 KB |
最終ジャッジ日時 | 2023-08-26 02:00:20 |
合計ジャッジ時間 | 12,054 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 118 ms
76,804 KB |
testcase_01 | AC | 118 ms
76,536 KB |
testcase_02 | AC | 118 ms
76,676 KB |
testcase_03 | AC | 153 ms
80,440 KB |
testcase_04 | AC | 147 ms
80,416 KB |
testcase_05 | AC | 160 ms
80,236 KB |
testcase_06 | AC | 147 ms
80,120 KB |
testcase_07 | AC | 161 ms
80,276 KB |
testcase_08 | AC | 147 ms
80,388 KB |
testcase_09 | AC | 154 ms
80,408 KB |
testcase_10 | AC | 117 ms
76,804 KB |
testcase_11 | AC | 118 ms
76,792 KB |
testcase_12 | AC | 120 ms
76,652 KB |
testcase_13 | AC | 118 ms
76,652 KB |
testcase_14 | AC | 119 ms
76,648 KB |
testcase_15 | AC | 118 ms
76,788 KB |
testcase_16 | AC | 218 ms
96,724 KB |
testcase_17 | AC | 297 ms
98,508 KB |
testcase_18 | AC | 210 ms
96,492 KB |
testcase_19 | AC | 376 ms
99,196 KB |
testcase_20 | AC | 391 ms
99,360 KB |
testcase_21 | AC | 426 ms
100,520 KB |
testcase_22 | AC | 304 ms
98,276 KB |
testcase_23 | AC | 321 ms
98,124 KB |
testcase_24 | AC | 322 ms
98,548 KB |
testcase_25 | AC | 395 ms
99,468 KB |
testcase_26 | AC | 378 ms
99,512 KB |
testcase_27 | AC | 386 ms
99,852 KB |
testcase_28 | AC | 374 ms
99,904 KB |
testcase_29 | AC | 376 ms
99,820 KB |
testcase_30 | AC | 401 ms
99,992 KB |
testcase_31 | AC | 374 ms
99,532 KB |
ソースコード
# import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') import sys from itertools import combinations, permutations, product, accumulate, groupby from collections import defaultdict, deque, Counter from functools import reduce from operator import add, mul import heapq import bisect import math import copy # sys.setrecursionlimit(10 ** 7) input = lambda: sys.stdin.readline().rstrip() INF = float("inf") MOD = 10 ** 9 + 7 from collections import defaultdict class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items()) N, M = map(int, input().split()) L = [[] for i in range(N+1)] for i in range(N): b, c = map(int, input().split()) L[c].append(b) uf = UnionFind(M + 1) cnt = 0 for l in L: for c in l: if not uf.same(l[0], c): uf.union(l[0], c) cnt += 1 print(cnt)