結果
問題 | No.1382 Travel in Mitaru city |
ユーザー | mkawa2 |
提出日時 | 2021-02-07 22:52:43 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 706 ms / 2,000 ms |
コード長 | 1,803 bytes |
コンパイル時間 | 74 ms |
コンパイル使用メモリ | 10,924 KB |
実行使用メモリ | 40,220 KB |
最終ジャッジ日時 | 2023-09-18 00:00:14 |
合計ジャッジ時間 | 26,523 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
8,156 KB |
testcase_01 | AC | 18 ms
8,052 KB |
testcase_02 | AC | 17 ms
7,996 KB |
testcase_03 | AC | 16 ms
8,160 KB |
testcase_04 | AC | 17 ms
8,164 KB |
testcase_05 | AC | 17 ms
8,044 KB |
testcase_06 | AC | 268 ms
18,168 KB |
testcase_07 | AC | 207 ms
15,928 KB |
testcase_08 | AC | 109 ms
12,896 KB |
testcase_09 | AC | 295 ms
18,972 KB |
testcase_10 | AC | 274 ms
18,288 KB |
testcase_11 | AC | 434 ms
27,988 KB |
testcase_12 | AC | 430 ms
28,580 KB |
testcase_13 | AC | 455 ms
29,144 KB |
testcase_14 | AC | 409 ms
27,676 KB |
testcase_15 | AC | 405 ms
27,984 KB |
testcase_16 | AC | 679 ms
39,960 KB |
testcase_17 | AC | 680 ms
40,084 KB |
testcase_18 | AC | 671 ms
39,972 KB |
testcase_19 | AC | 681 ms
39,944 KB |
testcase_20 | AC | 673 ms
40,096 KB |
testcase_21 | AC | 655 ms
40,076 KB |
testcase_22 | AC | 678 ms
39,984 KB |
testcase_23 | AC | 656 ms
39,968 KB |
testcase_24 | AC | 706 ms
40,044 KB |
testcase_25 | AC | 692 ms
40,068 KB |
testcase_26 | AC | 604 ms
40,052 KB |
testcase_27 | AC | 576 ms
40,016 KB |
testcase_28 | AC | 561 ms
39,988 KB |
testcase_29 | AC | 556 ms
39,996 KB |
testcase_30 | AC | 514 ms
39,952 KB |
testcase_31 | AC | 519 ms
34,796 KB |
testcase_32 | AC | 592 ms
40,220 KB |
testcase_33 | AC | 566 ms
38,084 KB |
testcase_34 | AC | 386 ms
29,052 KB |
testcase_35 | AC | 253 ms
21,992 KB |
testcase_36 | AC | 293 ms
35,208 KB |
testcase_37 | AC | 60 ms
12,488 KB |
testcase_38 | AC | 319 ms
38,132 KB |
testcase_39 | AC | 91 ms
16,020 KB |
testcase_40 | AC | 246 ms
30,848 KB |
testcase_41 | AC | 298 ms
33,244 KB |
testcase_42 | AC | 357 ms
38,788 KB |
testcase_43 | AC | 306 ms
34,432 KB |
testcase_44 | AC | 133 ms
18,796 KB |
testcase_45 | AC | 279 ms
32,200 KB |
testcase_46 | AC | 133 ms
16,956 KB |
testcase_47 | AC | 487 ms
37,828 KB |
testcase_48 | AC | 331 ms
28,892 KB |
testcase_49 | AC | 514 ms
39,864 KB |
testcase_50 | AC | 229 ms
22,792 KB |
testcase_51 | AC | 549 ms
35,568 KB |
testcase_52 | AC | 619 ms
40,176 KB |
testcase_53 | AC | 132 ms
15,968 KB |
testcase_54 | AC | 264 ms
23,264 KB |
testcase_55 | AC | 607 ms
39,276 KB |
testcase_56 | AC | 187 ms
18,956 KB |
testcase_57 | AC | 400 ms
29,176 KB |
testcase_58 | AC | 67 ms
12,000 KB |
testcase_59 | AC | 174 ms
18,536 KB |
testcase_60 | AC | 565 ms
38,080 KB |
testcase_61 | AC | 27 ms
8,620 KB |
testcase_62 | AC | 17 ms
8,108 KB |
testcase_63 | AC | 76 ms
9,176 KB |
testcase_64 | AC | 33 ms
8,588 KB |
testcase_65 | AC | 19 ms
8,048 KB |
testcase_66 | AC | 26 ms
8,588 KB |
testcase_67 | AC | 29 ms
8,484 KB |
testcase_68 | AC | 40 ms
8,444 KB |
testcase_69 | AC | 26 ms
8,532 KB |
testcase_70 | AC | 47 ms
8,860 KB |
ソースコード
import sys sys.setrecursionlimit(10**6) int1 = lambda x: int(x)-1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.buffer.readline()) def MI(): return map(int, sys.stdin.buffer.readline().split()) def MI1(): return map(int1, sys.stdin.buffer.readline().split()) def LI(): return list(map(int, sys.stdin.buffer.readline().split())) def LI1(): return list(map(int1, sys.stdin.buffer.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def BI(): return sys.stdin.buffer.readline().rstrip() def SI(): return sys.stdin.buffer.readline().rstrip().decode() # dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] dij = [[(-1, 0), (1, 0)], [(0, -1), (0, 1)]] inf = 10**16 md = 998244353 # md = 10**9+7 class UnionFind: def __init__(self, n): self.state = [-1] * n # self.size_table = [1] * n # cntはグループ数 # self.cnt = n def root(self, u): v = self.state[u] if v < 0: return u self.state[u] = res = self.root(v) return res def merge(self, u, v): ru = self.root(u) rv = self.root(v) if ru == rv: return du = self.state[ru] dv = self.state[rv] if du > dv: ru, rv = rv, ru if du == dv: self.state[ru] -= 1 self.state[rv] = ru # self.cnt -= 1 # self.size_table[ru] += self.size_table[rv] return n,m,s,t=MI() s,t=s-1,t-1 pp=LI() to=[[] for _ in range(n)] for _ in range(m): u,v=MI1() to[u].append(v) to[v].append(u) pu=[(p,u) for u,p in enumerate(pp)] pu.sort(reverse=True) pre=pp[s] uf=UnionFind(n) fin=[False]*n ans=0 for p,u in pu: fin[u]=True for v in to[u]: if fin[v]:uf.merge(u,v) if p<pre and uf.root(s)==uf.root(u): ans+=1 pre=p print(ans)