結果
問題 | No.1660 Matrix Exponentiation |
ユーザー |
|
提出日時 | 2021-07-23 05:29:24 |
言語 | Kotlin (2.1.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,831 bytes |
コンパイル時間 | 13,672 ms |
コンパイル使用メモリ | 447,460 KB |
実行使用メモリ | 110,900 KB |
最終ジャッジ日時 | 2024-11-21 00:08:32 |
合計ジャッジ時間 | 30,576 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 RE * 3 |
ソースコード
import java.io.PrintWriterimport java.util.*fun PrintWriter.solve() {val n = nextInt()val m = nextInt()val adj = Array(n) { mutableListOf<Int>() }val set = mutableSetOf<Pair<Int, Int>>()for (i in 0 until m) {val v1 = nextInt() - 1val v2 = nextInt() - 1if (v1 == v2 || set.contains(v2 to v1)) {println(-1)return}adj[v1].add(v2)set.add(v1 to v2)}if (findCycle(adj).isNotEmpty()) {println(-1)} else {val lst = topologicalSort(adj)val dp = IntArray(n) { -1 }fun dfs(v: Int): Int {if (dp[v] != -1) return dp[v]var max = 0for (w in adj[v]) {max = maxOf(max, dfs(w))}dp[v] = max + 1return dp[v]}lst.forEach { dfs(it) }println(dp.maxOrNull()!!)}}fun findCycle(adj: Array<MutableList<Int>>): List<Int> {val n = adj.sizeval seen = BooleanArray(n) { false }val finished = BooleanArray(n) { false }var pos = -1val hist = Stack<Int>()fun dfs(v: Int, p: Int) {seen[v] = truehist.push(v)for (w in adj[v]) {if (w == p) continueif (finished[w]) continueif (seen[w] && !finished[w]) {pos = wreturn}dfs(w, v)if (pos != -1) return}hist.pop()finished[v] = true}for (i in 0 until n) {if (!finished[i]) {dfs(i, -1)if (pos != -1) break}}val cycle = mutableListOf<Int>()while (hist.isNotEmpty()) {val t = hist.pop()cycle.add(t)if (t == pos) break}return cycle}fun topologicalSort(adj: Array<MutableList<Int>>): List<Int> {val ans = mutableListOf<Int>()val n = adj.sizeval ind = IntArray(n) { 0 }for (i in 0 until n) {for (v in adj[i]) ind[v]++}val que: Queue<Int> = ArrayDeque()for (i in 0 until n) {if (ind[i] == 0) que.add(i)}while (que.isNotEmpty()) {val now = que.poll()ans.add(now)for (v in adj[now]) {ind[v]--if (ind[v] == 0) que.add(v)}}return ans}fun main() {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}// region Scannerprivate var st = StringTokenizer("")private val br = System.`in`.bufferedReader()fun next(): String {while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())return st.nextToken()}fun nextInt() = next().toInt()fun nextLong() = next().toLong()fun nextLine() = br.readLine()!!fun nextDouble() = next().toDouble()// endregion