結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー | yakamoto |
提出日時 | 2021-08-14 15:59:12 |
言語 | Kotlin (1.9.10) |
結果 |
AC
|
実行時間 | 1,499 ms / 2,500 ms |
コード長 | 5,411 bytes |
コンパイル時間 | 23,748 ms |
コンパイル使用メモリ | 446,936 KB |
実行使用メモリ | 119,104 KB |
最終ジャッジ日時 | 2023-08-03 05:51:25 |
合計ジャッジ時間 | 80,100 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 328 ms
59,292 KB |
testcase_01 | AC | 292 ms
53,004 KB |
testcase_02 | AC | 331 ms
59,372 KB |
testcase_03 | AC | 352 ms
59,368 KB |
testcase_04 | AC | 423 ms
61,056 KB |
testcase_05 | AC | 347 ms
59,332 KB |
testcase_06 | AC | 354 ms
57,620 KB |
testcase_07 | AC | 423 ms
61,668 KB |
testcase_08 | AC | 1,283 ms
106,116 KB |
testcase_09 | AC | 1,313 ms
98,436 KB |
testcase_10 | AC | 1,329 ms
107,756 KB |
testcase_11 | AC | 1,036 ms
96,928 KB |
testcase_12 | AC | 1,017 ms
93,592 KB |
testcase_13 | AC | 1,021 ms
95,788 KB |
testcase_14 | AC | 1,380 ms
110,460 KB |
testcase_15 | AC | 1,300 ms
110,008 KB |
testcase_16 | AC | 1,326 ms
104,204 KB |
testcase_17 | AC | 1,044 ms
98,620 KB |
testcase_18 | AC | 1,010 ms
93,844 KB |
testcase_19 | AC | 1,317 ms
99,312 KB |
testcase_20 | AC | 1,052 ms
102,280 KB |
testcase_21 | AC | 1,217 ms
99,936 KB |
testcase_22 | AC | 1,499 ms
112,772 KB |
testcase_23 | AC | 1,447 ms
114,952 KB |
testcase_24 | AC | 1,196 ms
103,312 KB |
testcase_25 | AC | 1,279 ms
105,624 KB |
testcase_26 | AC | 1,346 ms
116,832 KB |
testcase_27 | AC | 1,356 ms
116,712 KB |
testcase_28 | AC | 1,287 ms
119,104 KB |
testcase_29 | AC | 1,229 ms
116,884 KB |
testcase_30 | AC | 1,205 ms
113,448 KB |
testcase_31 | AC | 1,204 ms
117,168 KB |
testcase_32 | AC | 1,100 ms
104,164 KB |
testcase_33 | AC | 1,139 ms
101,784 KB |
testcase_34 | AC | 1,225 ms
117,304 KB |
testcase_35 | AC | 1,165 ms
112,816 KB |
testcase_36 | AC | 1,232 ms
117,116 KB |
testcase_37 | AC | 1,229 ms
115,264 KB |
testcase_38 | AC | 1,216 ms
103,124 KB |
testcase_39 | AC | 1,156 ms
93,212 KB |
testcase_40 | AC | 1,258 ms
101,460 KB |
testcase_41 | AC | 1,160 ms
93,908 KB |
testcase_42 | AC | 1,171 ms
98,832 KB |
testcase_43 | AC | 288 ms
52,816 KB |
testcase_44 | AC | 343 ms
59,232 KB |
testcase_45 | AC | 924 ms
85,492 KB |
testcase_46 | AC | 940 ms
83,344 KB |
testcase_47 | AC | 927 ms
85,568 KB |
testcase_48 | AC | 963 ms
85,976 KB |
testcase_49 | AC | 937 ms
87,160 KB |
testcase_50 | AC | 892 ms
85,548 KB |
コンパイルメッセージ
Main.kt:209:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debug(a: LongArray) { ^ Main.kt:213:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debug(a: IntArray) { ^ Main.kt:217:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debug(a: BooleanArray) { ^ Main.kt:221:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")} ^ Main.kt:223:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debugDim(A: Array<LongArray>) { ^ Main.kt:230:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debugDim(A: Array<IntArray>) { ^ Main.kt:237:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debugDim(A: Array<BooleanArray>) { ^ Main.kt:254:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()} ^
ソースコード
import java.io.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.lang.AssertionError import java.util.* import kotlin.math.abs import kotlin.math.max import kotlin.math.min val MOD = 1_000_000_007 fun findCycle(n: Int, m: Int, from: IntArray, to: IntArray): List<Int>? { data class Edge(val i: Int, val v: Int) // 外に出せ val que = IntArray(n + 10) val nodeFlag = IntArray(n) val visitedEdge = BooleanArray(m) val g = Array(n){ mutableListOf<Edge>()} for (i in 0 until m) { g[from[i]].add(Edge(i, to[i])) g[to[i]].add(Edge(i, from[i])) } fun dfs(rt: Int): List<Int>? { fun step(pos: Int, v: Int): List<Int>? { que[pos] = v nodeFlag[v] = 1 for (i in g[v].indices) { val e = g[v][i] if (visitedEdge[e.i]) continue visitedEdge[e.i] = true when(nodeFlag[e.v]) { 1 -> { val ix = que.indexOf(e.v) val ans = mutableListOf<Int>() for (j in ix..pos) { ans += que[j] } return ans } 0 -> { val res = step(pos + 1, e.v) if (res != null) return res } else -> {} } } nodeFlag[v] = 2 return null } return step(0, rt) } for (u in 0 until n) { if (nodeFlag[u] == 0) { val res = dfs(u) if (res != null) return res } } return null } fun packUGraph(n: Int, from: IntArray, to: IntArray): Array<IntArray> { val p = IntArray(n) val m = from.size for (i in 0 until m) { ++p[from[i]] ++p[to[i]] } val g = Array(n){IntArray(p[it])} for (i in 0 until m) { g[from[i]][--p[from[i]]] = to[i] g[to[i]][--p[to[i]]] = from[i] } return g } data class Point(val h: Int, val w: Int) class Solver(stream: InputStream, private val out: java.io.PrintWriter) { private val reader = BufferedReader(InputStreamReader(stream), 32768) fun solve() { val th = Thread(null, Runnable { solve2() }, "solve", 1 shl 26) th.start() th.join() } fun solve2() { val (H, W, M) = na(3) val (from, to) = na2(M, -1) for (i in 0 until M) { to[i] += H } val toP = Array(M){ Pair(Point(from[it], to[it]), it) }.toMap() val cycle = findCycle(H + W, M, from, to) if (cycle == null) { out.println(-1) return } debug{"cycle:$cycle"} val N = cycle.size var i = if (cycle.first() < H) 0 else 1 // Hスタートかどうか val ans = IntArray(N) for (j in 0 until N) { val i2 = (i + 1) % N val p = if (j % 2 == 0) Point(cycle[i], cycle[i2]) else Point(cycle[i2], cycle[i]) debug{"$j $p"} ans[j] = toP[p]!! i = i2 } out.println(N) out.println(ans.map{it+1}.joinToString(" ")) } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private var tokenizer: StringTokenizer? = null private fun next(): String { while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { tokenizer = StringTokenizer(reader.readLine()) } return tokenizer!!.nextToken() } private fun ni() = next().toInt() private fun nl() = next().toLong() private fun ns() = next() private fun na(n: Int, offset: Int = 0): IntArray { return IntArray(n) { ni() + offset } } private fun nal(n: Int, offset: Int = 0): LongArray { val res = LongArray(n) for (i in 0 until n) { res[i] = nl() + offset } return res } private fun na2(n: Int, offset: Int = 0): Array<IntArray> { val a = Array(2){IntArray(n)} for (i in 0 until n) { for (e in a) { e[i] = ni() + offset } } return a } private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } /** * コーナーケースでエラー出たりするので、debug(dp[1])のように添え字付きの場合はdebug{}をつかうこと */ private inline fun debug(a: LongArray) { debug { a.joinToString(" ") } } private inline fun debug(a: IntArray) { debug { a.joinToString(" ") } } private inline fun debug(a: BooleanArray) { debug { toString(a) } } private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")} private inline fun debugDim(A: Array<LongArray>) { if (isDebug) { for (a in A) { debug(a) } } } private inline fun debugDim(A: Array<IntArray>) { if (isDebug) { for (a in A) { debug(a) } } } private inline fun debugDim(A: Array<BooleanArray>) { if (isDebug) { for (a in A) { debug(a) } } } /** * 勝手にimport消されるのを防ぎたい */ private fun hoge() { min(1, 2) max(1, 2) abs(-10) } private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()} private inline fun assert(b: Boolean, f: () -> String) = run{if (!b) throw AssertionError(f())} companion object { // TestRunnerから呼びたいので単純なmainじゃだめ fun main() { val out = java.io.PrintWriter(System.out) Solver(System.`in`, out).solve() out.flush() } } } /** * judgeから呼ばれる */ fun main() = Solver.main()