結果
問題 | No.1640 簡単な色塗り |
ユーザー | 👑 obakyan |
提出日時 | 2021-08-06 22:06:56 |
言語 | Lua (LuaJit 2.1.1696795921) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,186 bytes |
コンパイル時間 | 448 ms |
コンパイル使用メモリ | 5,316 KB |
実行使用メモリ | 29,608 KB |
最終ジャッジ日時 | 2023-09-12 02:06:32 |
合計ジャッジ時間 | 26,188 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
8,764 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 150 ms
20,404 KB |
testcase_05 | AC | 149 ms
20,516 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 883 ms
14,832 KB |
testcase_11 | AC | 455 ms
13,228 KB |
testcase_12 | AC | 354 ms
12,320 KB |
testcase_13 | AC | 1,342 ms
23,272 KB |
testcase_14 | AC | 1,942 ms
23,132 KB |
testcase_15 | AC | 213 ms
8,816 KB |
testcase_16 | AC | 302 ms
11,712 KB |
testcase_17 | AC | 1,378 ms
21,060 KB |
testcase_18 | AC | 28 ms
4,380 KB |
testcase_19 | AC | 362 ms
12,504 KB |
testcase_20 | AC | 586 ms
14,636 KB |
testcase_21 | AC | 422 ms
13,012 KB |
testcase_22 | AC | 16 ms
4,380 KB |
testcase_23 | AC | 681 ms
15,272 KB |
testcase_24 | AC | 85 ms
6,836 KB |
testcase_25 | AC | 516 ms
12,548 KB |
testcase_26 | AC | 1,165 ms
20,088 KB |
testcase_27 | AC | 195 ms
8,480 KB |
testcase_28 | AC | 1,242 ms
22,792 KB |
testcase_29 | AC | 1,131 ms
20,120 KB |
testcase_30 | AC | 19 ms
5,168 KB |
testcase_31 | AC | 190 ms
24,296 KB |
testcase_32 | AC | 157 ms
22,344 KB |
testcase_33 | AC | 87 ms
14,420 KB |
testcase_34 | AC | 152 ms
21,508 KB |
testcase_35 | AC | 75 ms
13,496 KB |
testcase_36 | AC | 20 ms
5,452 KB |
testcase_37 | AC | 30 ms
7,300 KB |
testcase_38 | AC | 154 ms
21,972 KB |
testcase_39 | AC | 60 ms
11,652 KB |
testcase_40 | AC | 52 ms
11,160 KB |
testcase_41 | AC | 103 ms
19,820 KB |
testcase_42 | AC | 58 ms
11,768 KB |
testcase_43 | AC | 79 ms
13,376 KB |
testcase_44 | AC | 67 ms
12,404 KB |
testcase_45 | AC | 55 ms
11,400 KB |
testcase_46 | AC | 19 ms
6,264 KB |
testcase_47 | AC | 15 ms
4,976 KB |
testcase_48 | AC | 186 ms
23,592 KB |
testcase_49 | AC | 7 ms
4,380 KB |
testcase_50 | AC | 1 ms
4,376 KB |
testcase_51 | AC | 1 ms
4,376 KB |
testcase_52 | AC | 313 ms
25,464 KB |
testcase_53 | TLE | - |
07_evil_01.txt | -- | - |
07_evil_02.txt | -- | - |
ソースコード
-- 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 if lvmax == lvinf then lvmax = level[a] end 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 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