#687329 (Lua) No.1640 簡単な色塗り

提出ソース

結果

問題	No.1640 簡単な色塗り
ユーザー	👑 obakyan
提出日時	2021-08-07 22:30:52
言語	Lua (LuaJit 2.1.1696795921)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	4,188 bytes
コンパイル時間	148 ms
コンパイル使用メモリ	6,944 KB
実行使用メモリ	32,256 KB
最終ジャッジ日時	2024-06-29 17:00:04
合計ジャッジ時間	26,189 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,624 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	97 ms 27,136 KB
testcase_05	AC	93 ms 27,136 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	554 ms 18,944 KB
testcase_11	AC	390 ms 16,640 KB
testcase_12	AC	318 ms 15,488 KB
testcase_13	AC	1,714 ms 29,184 KB
testcase_14	AC	1,153 ms 29,056 KB
testcase_15	AC	250 ms 11,136 KB
testcase_16	AC	360 ms 14,464 KB
testcase_17	AC	799 ms 25,984 KB
testcase_18	AC	21 ms 5,376 KB
testcase_19	AC	329 ms 15,360 KB
testcase_20	AC	500 ms 18,560 KB
testcase_21	AC	371 ms 16,256 KB
testcase_22	AC	14 ms 5,376 KB
testcase_23	AC	846 ms 19,456 KB
testcase_24	AC	87 ms 8,320 KB
testcase_25	AC	346 ms 15,616 KB
testcase_26	AC	672 ms 24,832 KB
testcase_27	AC	186 ms 10,880 KB
testcase_28	AC	1,104 ms 28,288 KB
testcase_29	AC	1,071 ms 24,576 KB
testcase_30	AC	18 ms 6,528 KB
testcase_31	AC	152 ms 30,976 KB
testcase_32	AC	126 ms 28,032 KB
testcase_33	AC	70 ms 18,432 KB
testcase_34	AC	113 ms 26,368 KB
testcase_35	AC	60 ms 17,408 KB
testcase_36	AC	16 ms 6,656 KB
testcase_37	AC	22 ms 8,960 KB
testcase_38	AC	111 ms 28,160 KB
testcase_39	AC	44 ms 14,336 KB
testcase_40	AC	41 ms 13,952 KB
testcase_41	AC	75 ms 24,704 KB
testcase_42	AC	46 ms 15,104 KB
testcase_43	AC	66 ms 16,512 KB
testcase_44	AC	57 ms 15,744 KB
testcase_45	AC	45 ms 13,824 KB
testcase_46	AC	18 ms 7,808 KB
testcase_47	AC	13 ms 6,016 KB
testcase_48	AC	145 ms 29,568 KB
testcase_49	AC	7 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	1 ms 5,376 KB
testcase_52	AC	213 ms 32,256 KB
testcase_53	TLE	-
07_evil_01.txt	TLE	-
07_evil_02.txt	TLE	-

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

ソースコード

raw source code

-- Hopcroft-Karp
ABmatch = {}
ABmatch.create = function(self, an, bn)
  self.dst = {}
  self.edge = {}
  for i = 1, an do
    self.dst[i] = false
    self.edge[i] = {}
  end
  self.src = {}
  self.invcnt = {}
  self.invs = {}
  self.invpos = {}
  self.padded = {}
  for i = 1, bn do
    self.src[i] = false
    self.invs[i] = {}
  end
  self.p = {}
  self.tasks = {}
  self.level = {}
end

ABmatch.addEdge = function(self, a, b)
  table.insert(self.edge[a], b)
  if not self.dst[a] and not self.src[b] then
    self.dst[a] = b
    self.src[b] = a
  end
end
ABmatch.makeAugPath = function(self)
  local tasknum = 0
  local tasks = self.tasks
  local level = self.level
  local edge = self.edge
  local src = self.src
  local an = #self.dst
  local bn = #src
  local invcnt, invs = self.invcnt, self.invs
  local p, psize = self.p, 0
  local padded = self.padded
  local lvinf = an + 1
  for i = 1, an do
    if self.dst[i] then
      level[i] = lvinf
    else
      tasknum = tasknum + 1
      tasks[tasknum] = i
      level[i] = 1
    end
  end
  for i = 1, bn do
    invcnt[i] = 0
    padded[i] = false
  end
  local done = 0
  local lvmax = lvinf
  while done < tasknum do
    done = done + 1
    local a = tasks[done]
    if lvmax < level[a] then break end
    for i = 1, #edge[a] do
      local b = edge[a][i]
      local sb = src[b]
      if sb then
        if level[sb] == lvinf then
          tasknum = tasknum + 1
          tasks[tasknum] = sb
          level[sb] = level[a] + 1
          invcnt[b] = invcnt[b] + 1
          invs[b][invcnt[b]] = a
        elseif level[sb] == level[a] + 1 then
          invcnt[b] = invcnt[b] + 1
          invs[b][invcnt[b]] = a
        end
      else
        lvmax = level[a]
        if padded[b] then
        else
          padded[b] = true
          psize = psize + 1
          p[psize] = b
        end
        invcnt[b] = invcnt[b] + 1
        invs[b][invcnt[b]] = a
      end
    end
  end
  self.psize = psize
  return lvmax
end

-- ABmatch.dfs = function(self, b, lv)
--   for i = 1, self.invcnt[b] do
--     local a = self.invs[b][i]
--     if self.level[a] == 1 or (self.level[a] == lv and self:dfs(self.dst[a], lv - 1)) then
--       self.dst[a], self.src[b] = b, a
--       self.level[a] = -1
--       return true
--     end
--   end
-- end

ABmatch.restore = function(self, bend, lvend)
  local invs, invcnt, invpos = self.invs, self.invcnt, self.invpos
  local dst, src, level = self.dst, self.src, self.level
  local bn = #src
  for i = 1, bn do
    invpos[i] = 0
  end
  local accept = false
  local tasks = self.tasks
  local taskpos = 1
  tasks[1] = bend
  while 0 < taskpos do
    local b = tasks[taskpos]
    if accept then
      local a = invs[b][invpos[b]]
      dst[a], src[b] = b, a
      level[a] = -1
      taskpos = taskpos - 1
    else
      if invpos[b] == invcnt[b] then
        level[src[b]] = -1
        taskpos = taskpos - 1
      else
        local ip = invpos[b] + 1
        invpos[b] = ip
        local a = invs[b][ip]
        if level[a] == 1 then
          accept = true
          dst[a], src[b] = b, a
          level[a] = -1
          taskpos = taskpos - 1
        elseif level[a] + taskpos == lvend + 1 then
          taskpos = taskpos + 1
          tasks[taskpos] = dst[a]
        end
      end
    end
  end
end

ABmatch.matching = function(self)
  local an = #self.dst
  local lv = self:makeAugPath()
  while lv <= an do
    for i = 1, self.psize do
      self:restore(self.p[i], lv)
      -- self:dfs(self.p[i], lv)
    end
    lv = self:makeAugPath()
  end
  self.executed = true
end

ABmatch.getMatchCount = function(self)
  if not self.executed then
    self:matching()
  end
  local cnt = 0
  for i = 1, #self.dst do
    if self.dst[i] then cnt = cnt + 1 end
  end
  return cnt
end

ABmatch.new = function(an, bn)
  local obj = {}
  setmetatable(obj, {__index = ABmatch})
  obj:create(an, bn)
  return obj
end

local n = io.read("*n")
local abm = ABmatch.new(n, n)
for i = 1, n do
  local a, b = io.read("*n", "*n")
  abm:addEdge(i, a)
  abm:addEdge(i, b)
end
if abm:getMatchCount() == n then
  print("Yes")
  for i = 1, n do
    print(abm.dst[i])
  end
else
  print("No")
end
-- print(os.clock())

yukicoder

結果

テストケース

ソースコード