結果
問題 | No.1473 おでぶなおばけさん |
ユーザー | 👑 obakyan |
提出日時 | 2021-05-24 16:02:44 |
言語 | Lua (LuaJit 2.1.1696795921) |
結果 |
AC
|
実行時間 | 383 ms / 2,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 6,944 KB |
実行使用メモリ | 32,768 KB |
最終ジャッジ日時 | 2024-04-21 01:55:43 |
合計ジャッジ時間 | 12,465 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 348 ms
31,488 KB |
testcase_03 | AC | 251 ms
27,008 KB |
testcase_04 | AC | 174 ms
18,560 KB |
testcase_05 | AC | 56 ms
8,576 KB |
testcase_06 | AC | 281 ms
27,904 KB |
testcase_07 | AC | 346 ms
32,128 KB |
testcase_08 | AC | 383 ms
32,768 KB |
testcase_09 | AC | 356 ms
32,128 KB |
testcase_10 | AC | 230 ms
17,792 KB |
testcase_11 | AC | 231 ms
17,792 KB |
testcase_12 | AC | 232 ms
17,792 KB |
testcase_13 | AC | 135 ms
12,800 KB |
testcase_14 | AC | 90 ms
9,856 KB |
testcase_15 | AC | 201 ms
16,512 KB |
testcase_16 | AC | 222 ms
17,408 KB |
testcase_17 | AC | 12 ms
6,944 KB |
testcase_18 | AC | 21 ms
6,940 KB |
testcase_19 | AC | 164 ms
16,256 KB |
testcase_20 | AC | 232 ms
24,832 KB |
testcase_21 | AC | 260 ms
21,760 KB |
testcase_22 | AC | 271 ms
29,184 KB |
testcase_23 | AC | 219 ms
26,368 KB |
testcase_24 | AC | 220 ms
23,808 KB |
testcase_25 | AC | 253 ms
28,416 KB |
testcase_26 | AC | 272 ms
27,136 KB |
testcase_27 | AC | 95 ms
12,032 KB |
testcase_28 | AC | 335 ms
31,744 KB |
testcase_29 | AC | 228 ms
21,632 KB |
testcase_30 | AC | 273 ms
24,320 KB |
testcase_31 | AC | 313 ms
32,128 KB |
testcase_32 | AC | 241 ms
28,544 KB |
testcase_33 | AC | 212 ms
23,168 KB |
testcase_34 | AC | 112 ms
13,696 KB |
testcase_35 | AC | 117 ms
14,080 KB |
testcase_36 | AC | 186 ms
20,224 KB |
testcase_37 | AC | 200 ms
25,216 KB |
testcase_38 | AC | 39 ms
6,940 KB |
testcase_39 | AC | 230 ms
17,792 KB |
testcase_40 | AC | 227 ms
17,664 KB |
testcase_41 | AC | 223 ms
17,536 KB |
testcase_42 | AC | 219 ms
17,664 KB |
testcase_43 | AC | 198 ms
25,472 KB |
testcase_44 | AC | 201 ms
25,472 KB |
testcase_45 | AC | 200 ms
25,600 KB |
testcase_46 | AC | 247 ms
23,296 KB |
testcase_47 | AC | 304 ms
29,056 KB |
testcase_48 | AC | 267 ms
27,008 KB |
ソースコード
local n, m = io.read("*n", "*n") local parent = {} local edge = {} local len = {} for i = 1, n do parent[i] = i edge[i] = {} len[i] = -1 end len[1] = 0 local function uf_findroot(idx) local idx_update = idx while parent[idx] ~= idx do idx = parent[idx] end while parent[idx_update] ~= idx do parent[idx_update], idx_update = idx, parent[idx_update] end return idx end local edgeinfo = {} for i = 1, m do edgeinfo[i] = {io.read("*n", "*n", "*n")} end table.sort(edgeinfo, function(a, b) return a[3] > b[3] end) local w = 0 for i = 1, m do local a, b = edgeinfo[i][1], edgeinfo[i][2] local c = edgeinfo[i][3] if c < w then break end table.insert(edge[a], b) table.insert(edge[b], a) local ra, rb = uf_findroot(a), uf_findroot(b) parent[rb], parent[b] = ra, ra local r1, rn = uf_findroot(1), uf_findroot(n) if r1 == rn then w = edgeinfo[i][3] end end local tasks = {1} local done = 0 while done < #tasks do done = done + 1 local src = tasks[done] for i = 1, #edge[src] do local dst = edge[src][i] if len[dst] < 0 then len[dst] = len[src] + 1 table.insert(tasks, dst) end end end print(w .. " " .. len[n])