#816025 (Lua) No.483 マッチ並べ

• 問題: No.483 マッチ並べ
• ユーザー: 👑 obakyan
• 提出日時: 2022-11-13 23:33:30
• 言語: Lua (LuaJit 2.1.1696795921)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 4,313 bytes
• コンパイル時間: 153 ms
• コンパイル使用メモリ: 6,816 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-15 04:58:06
• 合計ジャッジ時間: 1,995 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 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	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	3 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	3 ms; 5,376 KB
testcase_27	AC	4 ms; 5,376 KB
testcase_28	AC	3 ms; 5,376 KB
testcase_29	AC	4 ms; 5,376 KB
testcase_30	AC	3 ms; 5,376 KB
testcase_31	AC	4 ms; 5,376 KB
testcase_32	AC	4 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	3 ms; 5,376 KB
testcase_35	AC	2 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	3 ms; 5,376 KB
testcase_38	AC	3 ms; 5,376 KB
testcase_39	AC	3 ms; 5,376 KB
testcase_40	AC	4 ms; 5,376 KB
testcase_41	AC	4 ms; 5,376 KB
testcase_42	AC	4 ms; 5,376 KB
testcase_43	AC	3 ms; 5,376 KB
testcase_44	AC	2 ms; 5,376 KB
testcase_45	AC	2 ms; 5,376 KB
testcase_46	AC	2 ms; 5,376 KB
testcase_47	AC	3 ms; 5,376 KB
testcase_48	AC	4 ms; 5,376 KB
testcase_49	AC	3 ms; 5,376 KB
testcase_50	AC	4 ms; 5,376 KB
testcase_51	AC	3 ms; 5,376 KB
testcase_52	AC	3 ms; 5,376 KB
testcase_53	AC	1 ms; 5,376 KB
testcase_54	AC	2 ms; 5,376 KB
testcase_55	AC	2 ms; 5,376 KB

ソースコード

local SCCD = {}
SCCD.create = function(self, n)
  self.n = n
  self.asked, self.root = {}, {}
  self.edge, self.edge_asked = {}, {}
  self.invedge, self.invedge_asked = {}, {}
  for i = 1, n do
    self.asked[i] = false
    self.root[i] = 0
    self.edge[i] = {}
    self.edge_asked[i] = 0
    self.invedge[i] = {}
    self.invedge_asked[i] = 0
  end
  self.edgeinfo = {}
end
SCCD.addEdge = function(self, src, dst)
  table.insert(self.edge[src], dst)
  table.insert(self.invedge[dst], src)
  table.insert(self.edgeinfo, src)
  table.insert(self.edgeinfo, dst)
end

SCCD.dfs = function(self, spos, dfs_way)
  local asked = self.asked
  local edge, edge_asked = self.edge, self.edge_asked
  local tasks = {spos}
  while 0 < #tasks do
    local src = tasks[#tasks]
    asked[src] = true
    table.remove(tasks)
    if edge_asked[src] == #edge[src] then
      table.insert(dfs_way, src)
    else
      table.insert(tasks, src)
      edge_asked[src] = edge_asked[src] + 1
      local dst = edge[src][edge_asked[src]]
      if not asked[dst] then
        table.insert(tasks, dst)
      end
    end
  end
end

SCCD.invdfs = function(self, spos, rootid)
  local asked, root = self.asked, self.root
  local invedge, invedge_asked = self.invedge, self.invedge_asked
  local tasks = {spos}
  while 0 < #tasks do
    local src = tasks[#tasks]
    root[src] = rootid
    table.remove(tasks)
    while invedge_asked[src] < #invedge[src] do
      invedge_asked[src] = invedge_asked[src] + 1
      local dst = invedge[src][invedge_asked[src]]
      if asked[dst] and root[dst] == 0 then
        table.insert(tasks, src)
        table.insert(tasks, dst)
        break
      end
    end
  end
end

SCCD.categorize = function(self)
  local asked, root = self.asked, self.root
  for src = 1, self.n do
    if not asked[src] then
      local dfs_way = {}
      self:dfs(src, dfs_way)
      for i = #dfs_way, 1, -1 do
        local src = dfs_way[i]
        if root[src] == 0 then
          self:invdfs(src, src)
        end
      end
    end
  end
end


SCCD.make_group_graph = function(self)
  self.gsize = {}
  self.gedge = {}
  self.gpcnt = {}
  self.glen = {}
  self.gmember = {}
  local gsize, gmember, glen = self.gsize, self.gmember, self.glen
  local gedge, gpcnt = self.gedge, self.gpcnt
  local root = self.root
  local edgeinfo = self.edgeinfo
  for i = 1, self.n do
    gsize[i] = 0
    gedge[i], gpcnt[i] = {}, 0
    glen[i] = 0
    gmember[i] = {}
  end
  for i = 1, self.n do
    local r = root[i]
    gsize[r] = gsize[r] + 1
    table.insert(gmember[r], i)
  end
  for i = 1, #edgeinfo, 2 do
    local a, b = edgeinfo[i], edgeinfo[i + 1]
    local ra, rb = root[a], root[b]
    if ra ~= rb then
      table.insert(gedge[ra], rb)
      gpcnt[rb] = gpcnt[rb] + 1
    end
  end
end

SCCD.toposort = function(self)
  self:make_group_graph()
  local gsize, gedge, gpcnt = self.gsize, self.gedge, self.gpcnt
  local topoary = {}
  self.topoary = topoary
  local topo_tasks = {}
  for i = 1, self.n do
    if 0 < gsize[i] and gpcnt[i] == 0 then
      table.insert(topo_tasks, i)
    end
  end
  local topo_done = 0
  while topo_done < #topo_tasks do
    topo_done = topo_done + 1
    local g = topo_tasks[topo_done]
    topoary[topo_done] = g
    for i = 1, #gedge[g] do
      local dst = gedge[g][i]
      gpcnt[dst] = gpcnt[dst] - 1
      if gpcnt[dst] == 0 then
        table.insert(topo_tasks, dst)
      end
    end
  end
  return topoary
end

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

local n = io.read("*n")
local p1, p2 = {}, {}
local w = 111
for i = 1, n do
  local r, c = io.read("*n", "*n")
  p1[i] = (r - 1) * w + c
  r, c = io.read("*n", "*n")
  p2[i] = (r - 1) * w + c
end

local sccd = SCCD.new(2 * n)
for i = 1, n - 1 do
  for j = i + 1, n do
    if p1[i] == p1[j] then
      sccd:addEdge(i, n + j)
      sccd:addEdge(j, n + i)
    elseif p1[i] == p2[j] then
      sccd:addEdge(i, j)
      sccd:addEdge(n + j, n + i)
    elseif p2[i] == p1[j] then
      sccd:addEdge(n + i, n + j)
      sccd:addEdge(j, i)
    elseif p2[i] == p2[j] then
      sccd:addEdge(n + i, j)
      sccd:addEdge(n + j, i)
    end
  end
end
sccd:categorize()
for i = 1, n do
  if sccd.root[i] == sccd.root[n + i] then
    print("NO") os.exit()
  end
end
print("YES")