結果
問題 | No.1813 Magical Stones |
ユーザー | MasKoaTS |
提出日時 | 2022-01-13 22:58:15 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,730 ms / 2,000 ms |
コード長 | 2,862 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 69,928 KB |
最終ジャッジ日時 | 2024-04-28 21:14:30 |
合計ジャッジ時間 | 28,678 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
11,776 KB |
testcase_01 | AC | 41 ms
11,776 KB |
testcase_02 | AC | 37 ms
11,776 KB |
testcase_03 | AC | 482 ms
63,432 KB |
testcase_04 | AC | 39 ms
11,648 KB |
testcase_05 | AC | 38 ms
11,776 KB |
testcase_06 | AC | 58 ms
14,208 KB |
testcase_07 | AC | 38 ms
11,776 KB |
testcase_08 | AC | 42 ms
12,288 KB |
testcase_09 | AC | 46 ms
12,672 KB |
testcase_10 | AC | 42 ms
12,160 KB |
testcase_11 | AC | 320 ms
29,212 KB |
testcase_12 | AC | 37 ms
11,776 KB |
testcase_13 | AC | 37 ms
11,776 KB |
testcase_14 | AC | 498 ms
63,308 KB |
testcase_15 | AC | 1,538 ms
69,872 KB |
testcase_16 | AC | 1,502 ms
69,660 KB |
testcase_17 | AC | 1,333 ms
62,044 KB |
testcase_18 | AC | 1,496 ms
69,792 KB |
testcase_19 | AC | 1,541 ms
69,920 KB |
testcase_20 | AC | 1,555 ms
69,660 KB |
testcase_21 | AC | 1,730 ms
69,648 KB |
testcase_22 | AC | 1,518 ms
69,928 KB |
testcase_23 | AC | 1,509 ms
69,660 KB |
testcase_24 | AC | 47 ms
12,416 KB |
testcase_25 | AC | 206 ms
22,528 KB |
testcase_26 | AC | 75 ms
15,360 KB |
testcase_27 | AC | 1,054 ms
55,124 KB |
testcase_28 | AC | 1,137 ms
48,424 KB |
testcase_29 | AC | 1,204 ms
57,144 KB |
testcase_30 | AC | 1,052 ms
53,392 KB |
testcase_31 | AC | 1,372 ms
67,512 KB |
testcase_32 | AC | 38 ms
11,776 KB |
testcase_33 | AC | 36 ms
11,648 KB |
testcase_34 | AC | 67 ms
13,440 KB |
testcase_35 | AC | 145 ms
15,744 KB |
testcase_36 | AC | 58 ms
14,080 KB |
testcase_37 | AC | 320 ms
21,056 KB |
testcase_38 | AC | 389 ms
45,580 KB |
testcase_39 | AC | 1,032 ms
57,096 KB |
testcase_40 | AC | 59 ms
13,696 KB |
testcase_41 | AC | 64 ms
12,928 KB |
testcase_42 | AC | 146 ms
15,872 KB |
testcase_43 | AC | 107 ms
15,488 KB |
ソースコード
import itertools as iter import collections as coll import heapq as hq import bisect as bis from decimal import Decimal as dec from copy import deepcopy as dcopy import math import sys sys.setrecursionlimit(10**6) def input(): return sys.stdin.readline().rstrip() def getN(): return int(sys.stdin.readline()) def getNs(): return map(int,sys.stdin.readline().split()) def getList(): return list(map(int,sys.stdin.readline().split())) def strinps(n): return [sys.stdin.readline().rstrip() for _ in range(n)] pi = 3.141592653589793 mod = 10**9+7 MOD = 998244353 INF = math.inf dx = [1,0,-1,0]; dy = [0,1,0,-1] """ 強連結成分分解(SCC) from : https://github.com/ryusuke920/kyopro_educational_90_python/blob/main/solve_python/021.py ref : https://manabitimes.jp/math/1250 """ 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) #SCCグラフの構成 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 #SCCグラフを作る上でのDFS 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()) #逆向きDFS 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 #構成し終えたSCCグラフを連結成分ごとにリストにする 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 = getNs() route = [[] for _ in [0] * n] scc = SCC(n) for _ in [0] * m: a,b = [i - 1 for i in getNs()] route[a].append(b) scc.add_edge(a,b) scc.build() dag, _ = scc.construct() s = len(dag) if(s == 1): print(0) exit(0) source = [True] * s sink = [True] * s for i in range(s): for j in dag[i]: sink[i] = source[j] = False print(max(sum(source), sum(sink)))