結果
問題 | No.1813 Magical Stones |
ユーザー | yudedako |
提出日時 | 2022-01-30 23:42:14 |
言語 | Scala(Beta) (3.4.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,449 bytes |
コンパイル時間 | 15,836 ms |
コンパイル使用メモリ | 261,676 KB |
実行使用メモリ | 104,952 KB |
最終ジャッジ日時 | 2023-09-02 01:52:12 |
合計ジャッジ時間 | 82,914 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 931 ms
62,912 KB |
testcase_01 | AC | 918 ms
62,788 KB |
testcase_02 | AC | 910 ms
62,824 KB |
testcase_03 | AC | 1,191 ms
69,560 KB |
testcase_04 | AC | 913 ms
62,732 KB |
testcase_05 | AC | 939 ms
62,540 KB |
testcase_06 | AC | 1,045 ms
62,944 KB |
testcase_07 | AC | 937 ms
63,004 KB |
testcase_08 | AC | 960 ms
63,632 KB |
testcase_09 | AC | 985 ms
63,072 KB |
testcase_10 | AC | 970 ms
62,764 KB |
testcase_11 | AC | 1,400 ms
68,244 KB |
testcase_12 | AC | 931 ms
62,768 KB |
testcase_13 | AC | 925 ms
63,152 KB |
testcase_14 | AC | 1,164 ms
68,804 KB |
testcase_15 | AC | 1,973 ms
104,476 KB |
testcase_16 | AC | 1,992 ms
104,216 KB |
testcase_17 | AC | 1,905 ms
104,952 KB |
testcase_18 | AC | 1,946 ms
104,588 KB |
testcase_19 | AC | 1,991 ms
103,928 KB |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | AC | 1,992 ms
104,344 KB |
testcase_23 | AC | 1,978 ms
104,552 KB |
testcase_24 | AC | 1,012 ms
62,972 KB |
testcase_25 | AC | 1,329 ms
66,124 KB |
testcase_26 | AC | 1,283 ms
64,200 KB |
testcase_27 | AC | 1,875 ms
93,252 KB |
testcase_28 | AC | 1,935 ms
99,080 KB |
testcase_29 | AC | 1,893 ms
97,160 KB |
testcase_30 | AC | 1,974 ms
95,892 KB |
testcase_31 | AC | 1,972 ms
101,852 KB |
testcase_32 | AC | 942 ms
62,836 KB |
testcase_33 | AC | 926 ms
62,960 KB |
testcase_34 | AC | 1,216 ms
63,880 KB |
testcase_35 | AC | 1,271 ms
65,996 KB |
testcase_36 | AC | 1,037 ms
63,408 KB |
testcase_37 | AC | 1,398 ms
69,292 KB |
testcase_38 | AC | 1,437 ms
68,156 KB |
testcase_39 | AC | 1,847 ms
92,156 KB |
testcase_40 | AC | 1,078 ms
63,276 KB |
testcase_41 | AC | 1,249 ms
64,504 KB |
testcase_42 | AC | 1,266 ms
66,160 KB |
testcase_43 | AC | 1,287 ms
63,904 KB |
ソースコード
import scala.collection.mutable import scala.collection.mutable.ArrayBuffer import scala.io.StdIn.* import scala.math.* import scala.util.chaining.* object DAG: def dag(graph: Array[ArrayBuffer[Int]]): Array[Int] = val n = graph.length val indices = Array.fill(n){0} val stack = Array.fill(n){0} val size = Array.fill(n){0} var pos = 0 var outPos = n - 1 for i <- 0 until n do if indices(i) == 0 then stack(pos) = i pos += 1 while pos > 0 do pos -= 1 val top = stack(pos) val edge = graph(top) if indices(top) == edge.size then indices(top) = -1 stack(outPos) = top outPos -= 1 else var index = indices(top) while index < edge.length && indices(edge(index)) != 0 do size(edge(index)) += 1 index += 1 pos += 1 if index < edge.size then stack(pos) = edge(index) pos += 1 size(edge(index)) += 1 index += 1 indices(top) = index val reverseGraph = Array.tabulate(n){i => Array.fill(size(i)){0}} for from <- graph.indices do for to <- graph(from) do size(to) -= 1 reverseGraph(to)(size(to)) = from val newStack = size val result = indices for i <- stack do if result(i) < 0 then outPos += 1 result(i) = outPos newStack(pos) = i pos += 1 while pos > 0 do pos -= 1 val from = newStack(pos) for to <- reverseGraph(from) do if result(to) < 0 then result(to) = outPos size(pos) = to pos += 1 result @main def main = val Array(n, m) = readLine().split(' ').map(_.toInt) val edges = Array.fill(m){ val Array(a, b) = readLine().split(' ').map(_.toInt - 1) a -> b } val graph = Array.fill(n){ArrayBuffer[Int]()} for (a, b) <- edges do graph(a).append(b) val dag = DAG.dag(graph) val inDegree = Array.fill(dag.max + 1){0} val outDegree = Array.fill(inDegree.length){0} for (i, j) <- edges do val a = dag(i) val b = dag(j) if a != b then outDegree(a) += 1 inDegree(b) += 1 val greatest = inDegree.count(_ == 0) val smallest = outDegree.count(_ == 0) if inDegree.length == 1 then println(0) else println(max(greatest, smallest))