結果
問題 | No.1473 おでぶなおばけさん |
ユーザー | 👑 obakyan |
提出日時 | 2021-05-24 16:01:05 |
言語 | Lua (LuaJit 2.1.1696795921) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,144 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 5,248 KB |
実行使用メモリ | 32,768 KB |
最終ジャッジ日時 | 2024-04-21 01:54:22 |
合計ジャッジ時間 | 11,701 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 280 ms
31,616 KB |
testcase_03 | AC | 211 ms
26,880 KB |
testcase_04 | AC | 136 ms
18,560 KB |
testcase_05 | AC | 47 ms
8,704 KB |
testcase_06 | AC | 234 ms
28,032 KB |
testcase_07 | AC | 277 ms
32,128 KB |
testcase_08 | AC | 328 ms
32,768 KB |
testcase_09 | AC | 278 ms
32,128 KB |
testcase_10 | AC | 185 ms
17,792 KB |
testcase_11 | AC | 186 ms
17,792 KB |
testcase_12 | AC | 194 ms
17,792 KB |
testcase_13 | AC | 108 ms
12,928 KB |
testcase_14 | AC | 75 ms
9,856 KB |
testcase_15 | AC | 165 ms
16,640 KB |
testcase_16 | AC | 176 ms
17,408 KB |
testcase_17 | AC | 11 ms
5,376 KB |
testcase_18 | AC | 18 ms
5,376 KB |
testcase_19 | AC | 136 ms
16,256 KB |
testcase_20 | AC | 184 ms
24,832 KB |
testcase_21 | AC | 209 ms
21,760 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 265 ms
31,744 KB |
testcase_29 | WA | - |
testcase_30 | AC | 202 ms
24,192 KB |
testcase_31 | AC | 260 ms
32,128 KB |
testcase_32 | AC | 211 ms
28,544 KB |
testcase_33 | AC | 184 ms
23,296 KB |
testcase_34 | AC | 101 ms
13,696 KB |
testcase_35 | AC | 103 ms
14,080 KB |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | AC | 180 ms
17,920 KB |
testcase_40 | AC | 183 ms
17,664 KB |
testcase_41 | AC | 190 ms
17,664 KB |
testcase_42 | AC | 173 ms
17,664 KB |
testcase_43 | AC | 177 ms
25,472 KB |
testcase_44 | AC | 178 ms
25,472 KB |
testcase_45 | AC | 173 ms
25,472 KB |
testcase_46 | AC | 197 ms
23,296 KB |
testcase_47 | AC | 238 ms
29,056 KB |
testcase_48 | AC | 214 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] 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] break 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])