結果
問題 | No.778 クリスマスツリー |
ユーザー |
👑 |
提出日時 | 2019-09-17 08:55:54 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 818 ms / 2,000 ms |
コード長 | 2,812 bytes |
コンパイル時間 | 72 ms |
コンパイル使用メモリ | 5,248 KB |
実行使用メモリ | 78,080 KB |
最終ジャッジ日時 | 2024-10-14 02:01:05 |
合計ジャッジ時間 | 6,593 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
local mfl, mce, mmi = math.floor, math.ceil, math.minlocal SegTree = {}SegTree.updateAll = function(self)for i = self.stagenum - 1, 1, -1 dofor j = 1, self.cnt[i] doself.stage[i][j] = self.stage[i + 1][j * 2 - 1] + self.stage[i + 1][j * 2]endendendSegTree.create = function(self, n)local stagenum, mul = 1, 1self.cnt, self.stage, self.size = {1}, {{}}, {}while mul < n domul, stagenum = mul * 2, stagenum + 1self.cnt[stagenum], self.stage[stagenum] = mul, {}endfor i = 1, stagenum do self.size[i] = self.cnt[stagenum + 1 - i] endself.stagenum = stagenumfor i = 1, mul do self.stage[stagenum][i] = 0 endself:updateAll()endSegTree.getRange = function(self, right)local start_stage = 1while right < self.size[start_stage] dostart_stage = start_stage + 1endlocal ret = 0local t1, t2, t3 = {start_stage}, {1}, {right}while 0 < #t1 dolocal stage, l, r = t1[#t1], t2[#t1], t3[#t1]table.remove(t1) table.remove(t2) table.remove(t3)local sz = self.size[stage]if (l - 1) % sz ~= 0 thenlocal newr = mmi(r, mce((l - 1) / sz) * sz)table.insert(t1, stage + 1) table.insert(t2, l) table.insert(t3, newr)l = newr + 1endif sz <= r + 1 - l thenret = ret + self.stage[stage][mce(l / sz)]l = l + szendif l <= r thentable.insert(t1, stage + 1) table.insert(t2, l) table.insert(t3, r)endendreturn retendSegTree.setValue = function(self, idx, value, silent)self.stage[self.stagenum][idx] = valueif not silent thenfor i = self.stagenum - 1, 1, -1 dolocal dst = mce(idx / 2)local rem = dst * 4 - 1 - idxself.stage[i][dst] = self.stage[i + 1][idx] + self.stage[i + 1][rem]idx = dstendendendSegTree.new = function(n)local obj = {}setmetatable(obj, {__index = SegTree})obj:create(n)return objendlocal n = io.read("*n")local edge = {}local asked = {}local calced = {}for i = 1, n doedge[i] = {}asked[i] = falsecalced[i] = falseendcalced[1] = truefor i = 2, n dolocal a = 1 + io.read("*n")table.insert(edge[i], a)table.insert(edge[a], i)endlocal st = SegTree.new(n)local tasks = {1}local ret = 0while 0 < #tasks dolocal src = tasks[#tasks]table.remove(tasks)asked[src] = trueif not calced[src] thencalced[src] = trueret = ret + st:getRange(src - 1)endlocal haschild = falsewhile 0 < #edge[src] dolocal dst = edge[src][#edge[src]]if not asked[dst] thenst:setValue(src, 1)haschild = truetable.insert(tasks, src)table.insert(tasks, dst)table.remove(edge[src])breakelsetable.remove(edge[src])endendif not haschild thenst:setValue(src, 0)endendprint(ret)