結果
問題 | No.1813 Magical Stones |
ユーザー | MasKoaTS |
提出日時 | 2021-09-23 11:52:42 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,540 ms / 2,000 ms |
コード長 | 1,986 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 11,192 KB |
実行使用メモリ | 57,216 KB |
最終ジャッジ日時 | 2023-09-23 07:03:47 |
合計ジャッジ時間 | 25,621 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
8,524 KB |
testcase_01 | AC | 17 ms
8,432 KB |
testcase_02 | AC | 17 ms
8,568 KB |
testcase_03 | AC | 391 ms
53,180 KB |
testcase_04 | AC | 18 ms
8,120 KB |
testcase_05 | AC | 18 ms
8,596 KB |
testcase_06 | AC | 39 ms
10,408 KB |
testcase_07 | AC | 17 ms
8,580 KB |
testcase_08 | AC | 21 ms
8,944 KB |
testcase_09 | AC | 23 ms
9,128 KB |
testcase_10 | AC | 21 ms
8,928 KB |
testcase_11 | AC | 268 ms
23,604 KB |
testcase_12 | AC | 18 ms
8,484 KB |
testcase_13 | AC | 18 ms
8,080 KB |
testcase_14 | AC | 387 ms
53,116 KB |
testcase_15 | AC | 1,515 ms
56,964 KB |
testcase_16 | AC | 1,515 ms
57,152 KB |
testcase_17 | AC | 1,429 ms
47,752 KB |
testcase_18 | AC | 1,500 ms
57,216 KB |
testcase_19 | AC | 1,505 ms
56,908 KB |
testcase_20 | AC | 1,515 ms
56,832 KB |
testcase_21 | AC | 1,520 ms
56,976 KB |
testcase_22 | AC | 1,540 ms
56,784 KB |
testcase_23 | AC | 1,528 ms
56,944 KB |
testcase_24 | AC | 28 ms
9,108 KB |
testcase_25 | AC | 159 ms
18,096 KB |
testcase_26 | AC | 58 ms
11,684 KB |
testcase_27 | AC | 1,036 ms
44,984 KB |
testcase_28 | AC | 1,253 ms
38,736 KB |
testcase_29 | AC | 1,208 ms
46,368 KB |
testcase_30 | AC | 1,117 ms
43,520 KB |
testcase_31 | AC | 1,363 ms
55,120 KB |
testcase_32 | AC | 18 ms
8,416 KB |
testcase_33 | AC | 17 ms
8,424 KB |
testcase_34 | AC | 57 ms
9,904 KB |
testcase_35 | AC | 176 ms
11,744 KB |
testcase_36 | AC | 38 ms
10,320 KB |
testcase_37 | AC | 370 ms
16,456 KB |
testcase_38 | AC | 296 ms
37,712 KB |
testcase_39 | AC | 953 ms
46,760 KB |
testcase_40 | AC | 43 ms
10,124 KB |
testcase_41 | AC | 58 ms
9,368 KB |
testcase_42 | AC | 183 ms
11,960 KB |
testcase_43 | AC | 101 ms
11,728 KB |
ソースコード
""" Strongly Connected Component source ; https://github.com/ryusuke920/kyopro_educational_90_python/blob/main/solve_python/021.py """ class SCC: def __init__(self, n): self.n = n self.graph = [[] for _ in range(n)] self.rev_graph = [[] for _ in range(n)] self.labels = [-1] * n self.lb_cnt = 0 def add_edge(self, v, nxt_v): self.graph[v].append(nxt_v) self.rev_graph[nxt_v].append(v) def build(self): self.post_order = [] self.used = [False] * self.n for v in range(self.n): if(not self.used[v]): self._dfs(v) for v in reversed(self.post_order): if(self.labels[v] == -1): self._rev_dfs(v) self.lb_cnt += 1 def _dfs(self, v): stack = [v, 0] while(stack): v, idx = stack[-2:] if(not idx and self.used[v]): stack.pop() stack.pop() else: self.used[v] = True if(idx < len(self.graph[v])): stack[-1] += 1 stack.append(self.graph[v][idx]) stack.append(0) else: stack.pop() self.post_order.append(stack.pop()) def _rev_dfs(self, v): stack = [v] self.labels[v] = self.lb_cnt while(stack): v = stack.pop() for nxt_v in self.rev_graph[v]: if(self.labels[nxt_v] != -1): continue stack.append(nxt_v) self.labels[nxt_v] = self.lb_cnt def construct(self): self.dag = [[] for i in range(self.lb_cnt)] self.groups = [[] for i in range(self.lb_cnt)] for v, lb in enumerate(self.labels): for nxt_v in self.graph[v]: nxt_lb = self.labels[nxt_v] if(lb == nxt_lb): continue self.dag[lb].append(nxt_lb) self.groups[lb].append(v) return self.dag, self.groups """ Main Code """ n,m = map(int,input().split()) scc = SCC(n) for _ in range(m): a,b = map(int,input().split()) scc.add_edge(a-1,b-1) scc.build() DAG,_ = scc.construct() t = len(DAG) if(t <= 1): print(0) exit(0) source = [True]*t sink = [True]*t for i in range(t): for j in set(DAG[i]): source[i] = sink[j] = False ans = max(sum(source),sum(sink)) print(ans)