結果
問題 | No.1640 簡単な色塗り |
ユーザー | 👑 obakyan |
提出日時 | 2021-08-07 22:34:03 |
言語 | Lua (LuaJit 2.1.1696795921) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,180 bytes |
コンパイル時間 | 394 ms |
コンパイル使用メモリ | 7,136 KB |
実行使用メモリ | 29,452 KB |
最終ジャッジ日時 | 2023-09-12 03:58:50 |
合計ジャッジ時間 | 24,521 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
8,760 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 148 ms
20,376 KB |
testcase_05 | AC | 150 ms
20,368 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 596 ms
14,832 KB |
testcase_11 | AC | 624 ms
13,176 KB |
testcase_12 | AC | 354 ms
12,340 KB |
testcase_13 | AC | 1,876 ms
23,256 KB |
testcase_14 | AC | 1,298 ms
22,984 KB |
testcase_15 | AC | 210 ms
9,000 KB |
testcase_16 | AC | 288 ms
11,780 KB |
testcase_17 | AC | 924 ms
20,968 KB |
testcase_18 | AC | 27 ms
4,376 KB |
testcase_19 | AC | 352 ms
12,260 KB |
testcase_20 | AC | 811 ms
14,596 KB |
testcase_21 | AC | 405 ms
12,856 KB |
testcase_22 | AC | 16 ms
4,380 KB |
testcase_23 | AC | 940 ms
15,272 KB |
testcase_24 | AC | 85 ms
6,748 KB |
testcase_25 | AC | 359 ms
12,676 KB |
testcase_26 | AC | 790 ms
20,120 KB |
testcase_27 | AC | 197 ms
8,632 KB |
testcase_28 | AC | 1,184 ms
22,728 KB |
testcase_29 | AC | 766 ms
20,044 KB |
testcase_30 | AC | 19 ms
5,192 KB |
testcase_31 | AC | 177 ms
24,304 KB |
testcase_32 | AC | 150 ms
22,324 KB |
testcase_33 | AC | 86 ms
14,548 KB |
testcase_34 | AC | 143 ms
21,536 KB |
testcase_35 | AC | 72 ms
13,260 KB |
testcase_36 | AC | 19 ms
5,560 KB |
testcase_37 | AC | 28 ms
7,276 KB |
testcase_38 | AC | 144 ms
22,052 KB |
testcase_39 | AC | 57 ms
11,528 KB |
testcase_40 | AC | 51 ms
11,108 KB |
testcase_41 | AC | 101 ms
19,824 KB |
testcase_42 | AC | 58 ms
11,976 KB |
testcase_43 | AC | 79 ms
13,408 KB |
testcase_44 | AC | 65 ms
12,628 KB |
testcase_45 | AC | 56 ms
11,208 KB |
testcase_46 | AC | 19 ms
6,252 KB |
testcase_47 | AC | 15 ms
4,912 KB |
testcase_48 | AC | 179 ms
23,596 KB |
testcase_49 | AC | 7 ms
4,376 KB |
testcase_50 | AC | 1 ms
4,380 KB |
testcase_51 | AC | 1 ms
4,380 KB |
testcase_52 | AC | 302 ms
25,440 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 lvmax = level[a] if not padded[b] then 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())