結果
問題 | No.1293 2種類の道路 |
ユーザー | c-yan |
提出日時 | 2020-11-21 00:52:05 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 683 ms / 2,000 ms |
コード長 | 951 bytes |
コンパイル時間 | 79 ms |
コンパイル使用メモリ | 10,816 KB |
実行使用メモリ | 43,032 KB |
最終ジャッジ日時 | 2023-09-30 20:23:22 |
合計ジャッジ時間 | 10,062 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
7,880 KB |
testcase_01 | AC | 15 ms
7,800 KB |
testcase_02 | AC | 16 ms
7,748 KB |
testcase_03 | AC | 16 ms
7,800 KB |
testcase_04 | AC | 16 ms
7,864 KB |
testcase_05 | AC | 16 ms
7,792 KB |
testcase_06 | AC | 16 ms
7,924 KB |
testcase_07 | AC | 15 ms
7,784 KB |
testcase_08 | AC | 15 ms
8,300 KB |
testcase_09 | AC | 664 ms
36,520 KB |
testcase_10 | AC | 671 ms
36,416 KB |
testcase_11 | AC | 656 ms
36,352 KB |
testcase_12 | AC | 666 ms
36,320 KB |
testcase_13 | AC | 666 ms
36,356 KB |
testcase_14 | AC | 465 ms
42,872 KB |
testcase_15 | AC | 468 ms
43,032 KB |
testcase_16 | AC | 682 ms
38,092 KB |
testcase_17 | AC | 683 ms
38,156 KB |
testcase_18 | AC | 459 ms
38,496 KB |
testcase_19 | AC | 469 ms
36,884 KB |
testcase_20 | AC | 467 ms
36,632 KB |
testcase_21 | AC | 349 ms
8,196 KB |
testcase_22 | AC | 356 ms
8,332 KB |
testcase_23 | AC | 349 ms
8,556 KB |
ソースコード
from sys import setrecursionlimit, stdin def find(parent, i): t = parent[i] if t < 0: return i t = find(parent, t) parent[i] = t return t def unite(parent, i, j): i = find(parent, i) j = find(parent, j) if i == j: return parent[j] += parent[i] parent[i] = j readline = stdin.readline setrecursionlimit(10 ** 6) N, D, W = map(int, readline().split()) car = [-1] * N for _ in range(D): a, b = map(lambda x: int(x) - 1, readline().split()) unite(car, a, b) walking = [-1] * N for _ in range(W): c, d = map(lambda x: int(x) - 1, readline().split()) unite(walking, c, d) cs = [0] * N ss = [set() for _ in range(N)] for i in range(N): a = find(car, i) b = find(walking, i) if b in ss[a]: continue ss[a].add(b) cs[a] -= walking[b] result = 0 for i in range(N): if car[i] >= 0: continue result -= (cs[i] - 1) * car[i] print(result)