#626662 (Lua) No.1382 Travel in Mitaru city

提出ソース

結果

問題	No.1382 Travel in Mitaru city
ユーザー	👑 obakyan
提出日時	2021-03-07 23:14:21
言語	Lua (LuaJit 2.1.1696795921)
結果	AC
実行時間	239 ms / 2,000 ms
コード長	2,049 bytes
コンパイル時間	337 ms
コンパイル使用メモリ	5,632 KB
実行使用メモリ	17,664 KB
最終ジャッジ日時	2024-10-09 09:19:43
合計ジャッジ時間	11,240 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	69 ms 6,272 KB
testcase_07	AC	64 ms 5,888 KB
testcase_08	AC	40 ms 5,248 KB
testcase_09	AC	85 ms 6,656 KB
testcase_10	AC	80 ms 6,528 KB
testcase_11	AC	145 ms 11,136 KB
testcase_12	AC	146 ms 11,264 KB
testcase_13	AC	169 ms 11,520 KB
testcase_14	AC	132 ms 11,008 KB
testcase_15	AC	138 ms 11,008 KB
testcase_16	AC	239 ms 16,640 KB
testcase_17	AC	220 ms 16,512 KB
testcase_18	AC	231 ms 16,768 KB
testcase_19	AC	226 ms 16,512 KB
testcase_20	AC	236 ms 16,640 KB
testcase_21	AC	234 ms 16,640 KB
testcase_22	AC	232 ms 16,640 KB
testcase_23	AC	237 ms 16,640 KB
testcase_24	AC	236 ms 16,768 KB
testcase_25	AC	231 ms 16,640 KB
testcase_26	AC	200 ms 16,640 KB
testcase_27	AC	198 ms 16,512 KB
testcase_28	AC	207 ms 16,512 KB
testcase_29	AC	197 ms 16,512 KB
testcase_30	AC	183 ms 16,512 KB
testcase_31	AC	122 ms 14,080 KB
testcase_32	AC	147 ms 15,872 KB
testcase_33	AC	132 ms 15,104 KB
testcase_34	AC	94 ms 10,624 KB
testcase_35	AC	62 ms 8,576 KB
testcase_36	AC	85 ms 14,208 KB
testcase_37	AC	16 ms 5,248 KB
testcase_38	AC	93 ms 15,232 KB
testcase_39	AC	25 ms 5,760 KB
testcase_40	AC	70 ms 12,800 KB
testcase_41	AC	78 ms 13,568 KB
testcase_42	AC	93 ms 15,232 KB
testcase_43	AC	82 ms 13,952 KB
testcase_44	AC	34 ms 6,656 KB
testcase_45	AC	86 ms 13,184 KB
testcase_46	AC	50 ms 6,784 KB
testcase_47	AC	197 ms 16,896 KB
testcase_48	AC	136 ms 11,648 KB
testcase_49	AC	212 ms 17,664 KB
testcase_50	AC	89 ms 9,728 KB
testcase_51	AC	121 ms 14,336 KB
testcase_52	AC	148 ms 15,872 KB
testcase_53	AC	31 ms 5,760 KB
testcase_54	AC	62 ms 8,832 KB
testcase_55	AC	140 ms 15,488 KB
testcase_56	AC	43 ms 7,552 KB
testcase_57	AC	90 ms 10,752 KB
testcase_58	AC	14 ms 5,248 KB
testcase_59	AC	40 ms 6,656 KB
testcase_60	AC	136 ms 15,104 KB
testcase_61	AC	5 ms 5,248 KB
testcase_62	AC	2 ms 5,248 KB
testcase_63	AC	18 ms 5,248 KB
testcase_64	AC	8 ms 5,248 KB
testcase_65	AC	2 ms 5,248 KB
testcase_66	AC	4 ms 5,248 KB
testcase_67	AC	5 ms 5,248 KB
testcase_68	AC	8 ms 5,248 KB
testcase_69	AC	5 ms 5,248 KB
testcase_70	AC	11 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

local bls, brs = bit.lshift, bit.rshift
local Heapq = {}
Heapq.create = function(self, lt)
  self.lt = lt
  self.cnt = 0
  self.t = {}
end

Heapq.push = function(self, v)
  local hqlt = self.lt
  local hqt = self.t
  local c = self.cnt + 1
  self.cnt = c
  hqt[c] = v
  while 1 < c do
    local p = brs(c, 1)
    if hqlt(hqt[c], hqt[p]) then
      hqt[c], hqt[p] = hqt[p], hqt[c]
      c = p
    else
      break
    end
  end
end
Heapq.empty = function(self)
  return self.cnt == 0
end
Heapq.pop = function(self)
  local hqlt = self.lt
  local hqt = self.t
  local ret = hqt[1]
  local c = self.cnt
  hqt[1] = hqt[c]
  c = c - 1
  self.cnt = c
  local p = 1
  while true do
    local d1, d2 = p * 2, p * 2 + 1
    if c < d1 then break
    elseif c < d2 then
      if hqlt(hqt[d1], hqt[p]) then
        hqt[d1], hqt[p] = hqt[p], hqt[d1]
      end
      break
    else
      if hqlt(hqt[d1], hqt[d2]) then
        if hqlt(hqt[d1], hqt[p]) then
          hqt[d1], hqt[p] = hqt[p], hqt[d1]
          p = d1
        else break
        end
      else
        if hqlt(hqt[d2], hqt[p]) then
          hqt[d2], hqt[p] = hqt[p], hqt[d2]
          p = d2
        else break
        end
      end
    end
  end
  return ret
end

Heapq.new = function(lt)
  local obj = {}
  setmetatable(obj, {__index = Heapq})
  obj:create(lt)
  return obj
end

local n, m = io.read("*n", "*n")
local spos, tpos = io.read("*n", "*n")
local p = {}
local edge = {}
local asked = {}
for i = 1, n do
  p[i] = io.read("*n")
  edge[i] = {}
  asked[i] = false
end
for i = 1, m do
  local a, b = io.read("*n", "*n")
  table.insert(edge[a], b)
  table.insert(edge[b], a)
end
local function hqlt(a, b)
  return p[a] > p[b]
end
local hq = Heapq.new(hqlt)
asked[spos] = true
hq:push(spos)

local ret = 0
local curval = p[spos]
while not hq:empty() do
  local v = hq:pop()
  if p[v] < curval then
    ret = ret + 1
    curval = p[v]
  end
  for i = 1, #edge[v] do
    local dst = edge[v][i]
    if not asked[dst] then
      asked[dst] = true
      hq:push(dst)
    end
  end
end
print(ret)

yukicoder

結果

テストケース

ソースコード