結果
問題 | No.1660 Matrix Exponentiation |
ユーザー |
|
提出日時 | 2021-07-23 08:17:46 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 1,226 ms / 2,000 ms |
コード長 | 2,354 bytes |
コンパイル時間 | 15,844 ms |
コンパイル使用メモリ | 450,112 KB |
実行使用メモリ | 135,988 KB |
最終ジャッジ日時 | 2024-06-23 07:08:02 |
合計ジャッジ時間 | 33,258 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.PrintWriterimport java.util.*import kotlin.math.*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 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]}(0 until n).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 main() {Thread(null, {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}, "solve", 1.shl(26)).start()}// 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