結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 15:04:26 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 1,144 ms / 3,000 ms |
コード長 | 24,009 bytes |
コンパイル時間 | 20,282 ms |
コンパイル使用メモリ | 307,260 KB |
実行使用メモリ | 125,952 KB |
最終ジャッジ日時 | 2024-12-27 04:32:52 |
合計ジャッジ時間 | 45,680 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
def int(b = 0)read_line.to_i64 + benddef ints(b = 0)read_line.split.map { |x| x.to_i64 + b }enddef strread_line.chompendmacro chmax(a, b)({{a}} < {{b}} && ({{a}} = {{b}}))endmacro chmin(a, b)({{a}} > {{b}} && ({{a}} = {{b}}))endmacro make_array(s, x)Array.new({{ s[0] }}) {{% if s[1..s.size].empty? %}; {{ x }}{% else %}; make_array({{ s[1..s.size] }}, {{ x }}) {% end %}}endOO = (1_i64 << 62) - (1_i64 << 31)module NgLib# 不変な数列 $A$ に対して、$\sum_{i=l}^{r-1} A_i$ を前計算 $O(N)$ クエリ $O(1)$ で求めます。class StaticRangeSum(T)getter size : Int64getter csum : Array(T)# 配列 `array` に対して累積和を構築します。## ```# array = [1, 1, 2, 3, 5, 8, 13]# csum = StaticRangeSum(Int32).new(array)# ```def initialize(array : Array(T))@size = array.size.to_i64@csum = Array.new(@size + 1, T.zero)@size.times { |i| @csum[i + 1] = @csum[i] + array[i] }end# $[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。## ```# array = [1, 1, 2, 3, 5, 8, 13]# csum = StaticRangeSum(Int32).new(array)# csum.get(0...5) # => 1 + 1 + 2 + 3 + 5 = 12# ```def get(l, r) : Traise IndexError.new("`l` must be less than or equal to `r` (#{l}, #{r})") unless l <= r@csum[r] - @csum[l]end# :ditto:def get(range : Range(Int?, Int?)) : Tl = (range.begin || 0)r = if range.end.nil?@sizeelserange.end.not_nil! + (range.exclusive? ? 0 : 1)endget(l, r)end# $[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。## $l \leq r$ を満たさないとき、`nil` を返します。## ```# array = [1, 1, 2, 3, 5, 8, 13]# csum = StaticRangeSum(Int32).new(array)# csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12# csum.get?(7...5) # => nil# ```def get?(l, r) : T?return nil unless l <= rget(l, r)end# :ditto:def get?(range : Range(Int?, Int?)) : T?l = (range.begin || 0)r = if range.end.nil?@sizeelserange.end.not_nil! + (range.exclusive? ? 0 : 1)endget?(l, r)end# $\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。def get!(l, r) : T@csum[r] - @csum[l]end# :ditto:def get!(range : Range(Int?, Int?)) : Tl = (range.begin || 0)r = if range.end.nil?@sizeelserange.end.not_nil! + (range.exclusive? ? 0 : 1)endget!(l, r)end# `get(l : Int, r : Int)` へのエイリアスです。def [](l, r) : Tget(l, r)end# `get(range : Range(Int?, Int?))` へのエイリアスです。def [](range : Range(Int?, Int?)) : Tget(range)end# `get(l : Int, r : Int)` へのエイリアスです。def []?(l, r) : T?get?(l, r)end# `get?(range : Range(Int?, Int?))` へのエイリアスです。def []?(range : Range(Int?, Int?)) : T?get?(range)endendendmodule NgLib# 不変な数列 $A$ について、以下の条件を満たす演算を、区間クエリとして処理します。# - 結合則 : $(x \oplus y) \oplus z = x \oplus (y \oplus z)$# - 冪等性 : $x \oplus x = x$## 前計算は $O(N \log{N})$ かかりますが、区間クエリには $O(1)$ で答えられます。class SparseTable(T)getter size : Int32@data : Array(T)@table : Array(Array(T))@lookup : Array(Int32)@op : (T, T) -> T# $\oplus = \max$ としてデータ構造を構築します。def self.max(elems : Enumerable(T))new elems, ->(x : T, y : T) { x > y ? x : y }end# $\oplus = \min$ としてデータ構造を構築します。def self.min(elems : Enumerable(T))new elems, ->(x : T, y : T) { x < y ? x : y }end# $\oplus = \mathrm{bitwise-or}$ としてデータ構造を構築します。def self.bitwise_or(elems : Enumerable(T))new elems, ->(x : T, y : T) { x | y }end# $\oplus = \mathrm{bitwise-and}$ としてデータ構造を構築します。def self.bitwise_and(elems : Enumerable(T))new elems, ->(x : T, y : T) { x & y }end# $\oplus = \mathrm{gcd}$ としてデータ構造を構築します。def self.gcd(elems : Enumerable(T))new elems, ->(x : T, y : T) { x.gcd(y) }end# $\oplus = op$ としてデータ構造を構築します。def initialize(elems : Enumerable(T), @op : (T, T) -> T)@size = elems.size@data = Array(T).newlog = (0..).index! { |k| (1 << k) > @size }@table = Array.new(log) { Array(T).new(1 << log, T.zero) }elems.each_with_index { |e, i| @table[0][i] = e; @data << e }(1...log).each do |i|j = 0while j + (1 << i) <= (1 << log)@table[i][j] = @op.call(@table[i - 1][j], @table[i - 1][j + (1 << (i - 1))])j += 1endend@lookup = [0] * (@size + 1)(2..@size).each do |i|@lookup[i] = @lookup[i >> 1] + 1endend# `range` の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。## ```# rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])# rmq.prod(0...3) # => 1# ```def prod(range : Range(Int?, Int?))l = (range.begin || 0)r = if range.end.nil?@sizeelserange.end.not_nil! + (range.exclusive? ? 0 : 1)endb = @lookup[r - l]@op.call(@table[b][l], @table[b][r - (1 << b)])end# `range` の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。## $0 \leq l \leq r \leq n$ を満たさないとき、`nil` を返します。## ```# rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])# rmq.prod(0...3) # => 1# ```def prod?(range : Range(Int?, Int?))l = (range.begin || 0)r = if range.end.nil?@sizeelserange.end.not_nil! + (range.exclusive? ? 0 : 1)endreturn nil unless 0 <= l && l <= r && r <= @sizeprod(range)end# $a_i$ を返します。def [](i)@data[i]end# $a_i$ を返します。## 添字が範囲外のとき、`nil` を返します。def []?(i)@data[i]?end# `prod` へのエイリアスです。def [](range : Range(Int?, Int?))prod(range)end# `prod?` へのエイリアスです。def []?(range : Range(Int?, Int?))prod?(range)endendendclass StronglyConnectedComponentsalias Graph = Array(Array(Int64))getter leader : Array(Int64)getter graph : Graphgetter groups : Array(Array(Int64))@n : Int64@order : Array(Int64)@fwd : Graph@bwd : Graph@closed : Array(Bool)def initialize(@fwd : Graph)@n = @fwd.size.to_i64@order = Array(Int64).new(@n)@leader = Array.new(@n, -1_i64)@bwd = Array.new(@n){ Array(Int64).new }@n.times do |i|@fwd[i].each do |j|@bwd[j] << iendend@closed = Array(Bool).new(@n, false)@n.times{ |i| dfs(i) }@order = @order.reverseptr = rdfs@graph = Array.new(ptr){ Array(Int64).new }@groups = Array.new(ptr){ Array(Int64).new }@n.times do |i|@groups[@leader[i]] << i@fwd[i].each do |j|x, y = @leader[i], @leader[j]next if x == y@graph[x] << yendendenddef same(u : Int, v : Int)leader[u] == leader[v]enddef size@groups.sizeenddef size(v : Int)@groups[leader[v]].sizeendprivate def dfs(i : Int)return if @closed[i]@closed[i] = true@fwd[i].each{ |j| dfs(j) }@order << iendprivate def rdfsptr = 0_i64closed = Array.new(@n, false)@order.each do |s|next if closed[s]que = Deque(Int64).newque << sclosed[s] = true@leader[s] = ptruntil que.empty?now = que.shift@bwd[now].each do |nxt|next if closed[nxt]closed[nxt] = true@leader[nxt] = ptrque << nxtendendptr += 1endptrendendstruct Int64def self.infOOendendmodule NgLibstruct Edge@data : {Int64, Int64}def initialize(t : Int64, w : Int64)@data = {t, w}enddef self.to@data[0]enddef self.weight@data[1]enddef [](i : Int)@data[i]endendend# ac-library.cr by hakatashi https://github.com/google/ac-library.cr## Copyright 2023 Google LLC## Licensed under the Apache License, Version 2.0 (the "License");# you may not use this file except in compliance with the License.# You may obtain a copy of the License at## https://www.apache.org/licenses/LICENSE-2.0## Unless required by applicable law or agreed to in writing, software# distributed under the License is distributed on an "AS IS" BASIS,# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.# See the License for the specific language governing permissions and# limitations under the License.module AtCoder# Implements standard priority queue like [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue).## ```# q = AtCoder::PriorityQueue(Int64).new# q << 1_i64# q << 3_i64# q << 2_i64# q.pop # => 3# q.pop # => 2# q.pop # => 1# ```class PriorityQueue(T)include Enumerable(T)getter heap : Array(T)# Create a new queue in ascending order of priority.def self.maxself.new { |a, b| a <= b }end# Create a new queue in ascending order of priority with the elements in *enumerable*.def self.max(enumerable : Enumerable(T))self.new(enumerable) { |a, b| a <= b }end# Create a new queue in descending order of priority.def self.minself.new { |a, b| a >= b }end# Create a new queue in descending order of priority with the elements in *enumerable*.def self.min(enumerable : Enumerable(T))self.new(enumerable) { |a, b| a >= b }enddef initializeinitialize { |a, b| a <= b }end# Initializes queue with the elements in *enumerable*.def self.new(enumerable : Enumerable(T))self.new(enumerable) { |a, b| a <= b }end# Initializes queue with the custom comperator.## If the second argument `b` should be popped earlier than# the first argument `a`, return `true`. Else, return `false`.## ```# q = AtCoder::PriorityQueue(Int64).new { |a, b| a >= b }# q << 1_i64# q << 3_i64# q << 2_i64# q.pop # => 1# q.pop # => 2# q.pop # => 3# ```def initialize(&block : T, T -> Bool)@heap = Array(T).new@compare_proc = blockend# Initializes queue with the elements in *enumerable* and the custom comperator.## If the second argument `b` should be popped earlier than# the first argument `a`, return `true`. Else, return `false`.## ```# q = AtCoder::PriorityQueue.new([1, 3, 2]) { |a, b| a >= b }# q.pop # => 1# q.pop # => 2# q.pop # => 3# ```def initialize(enumerable : Enumerable(T), &block : T, T -> Bool)@heap = enumerable.to_a@compare_proc = blocklen = @heap.size(len // 2 - 1).downto(0) do |parent|v = @heap[parent]child = parent * 2 + 1while child < lenif child + 1 < len && @compare_proc.call(@heap[child], @heap[child + 1])child += 1endunless @compare_proc.call(v, @heap[child])breakend@heap[parent] = @heap[child]parent = childchild = parent * 2 + 1end@heap[parent] = vendend# Pushes value into the queue.def push(v : T)@heap << vindex = @heap.size - 1while index != 0parent = (index - 1) // 2if @compare_proc.call(@heap[index], @heap[parent])breakend@heap[parent], @heap[index] = @heap[index], @heap[parent]index = parentendend# Alias of `push`def <<(v : T)push(v)end# Pops value from the queue.def popif @heap.size == 0return nilendif @heap.size == 1return @heap.popendret = @heap.first@heap[0] = @heap.popindex = 0while index * 2 + 1 < @heap.sizechild = if index * 2 + 2 < @heap.size && !@compare_proc.call(@heap[index * 2 + 2], @heap[index * 2 + 1])index * 2 + 2elseindex * 2 + 1endif @compare_proc.call(@heap[child], @heap[index])breakend@heap[child], @heap[index] = @heap[index], @heap[child]index = childendretend# Yields each item in the queue in comparator's order.def each(&)@heap.sort { |a, b| @compare_proc.call(a, b) ? 1 : -1 }.each do |e|yield eendend# Returns, but does not remove, the head of the queue.def first(&)@heap.first { yield }end# Returns `true` if the queue is empty.delegate :empty?, to: @heap# Returns size of the queue.delegate :size, to: @heapendendmodule NgLibabstract struct Weightinclude Comparable(Weight)def self.zero : selfenddef self.inf : selfenddef +(other : self)enddef <=>(other : self)endendclass DijkstraGraph(Weight)record Edge(W), target : Int32, weight : Wgetter size : Int32@graph : Array(Array(Edge(Weight)))# $n$ 頂点 $0$ 辺からなるグラフを作成します。## ```# graph = Dijkstra.new(n)# ```def initialize(n : Int)@size = n.to_i32@graph = Array.new(@size) { Array(Edge(Weight)).new }end# 非負整数の重み $w$ の辺 $(u, v)$ を追加します。## `directed` が `true` の場合、# 有向辺とみなして、$u$ から $v$ への辺のみ生やします。## ```# graph = Dijkstra.new(n)# graph.add_edge(u, v, w) # => (u) <---w---> (v)# graph.add_edge(u, v, w, directed: true) # => (u) ----w---> (v)# ```def add_edge(u : Int, v : Int, w : Weight, directed : Bool = false)@graph[u.to_i32] << Edge.new(v.to_i32, w)@graph[v.to_i32] << Edge.new(u.to_i32, w) unless directedend# 全点対間の最短経路長を返します。## ```# dists = graph.shortest_path# dists # => [[0, 1, 3], [1, 0, 2], [1, 1, 0]]# ```def shortest_path : Array(Array(Weight))(0...@size).map { |s| shortest_path(s) }end# 始点 `start` から各頂点への最短経路長を返します。## ```# dist = graph.shortest_path(2)# dist # => [3, 8, 0, 7, 1]# ```def shortest_path(start : Int) : Array(Weight)dist = [Weight.inf] * @sizedist[start] = Weight.zeronext_node = AtCoder::PriorityQueue({Weight, Int32}).minnext_node << {Weight.zero, start.to_i32}until next_node.empty?d, source = next_node.pop.not_nil!next if dist[source] < d@graph[source].each do |e|next_cost = dist[source] + e.weightif next_cost < dist[e.target]dist[e.target] = next_costnext_node << {next_cost, e.target}endendenddistend# 始点 `start` から終点 `dest` への最短経路長を返します。## ```# dist = graph.shortest_path(start: 2, dest: 0)# dist # => 12# ```def shortest_path(start : Int, dest : Int) : Weightshortest_path(start)[dest]end# 始点 `start` から終点 `dest` への最短経路の一例を返します。## ```# route = graph.shortest_path_route(start: 2, dest: 0)# route # => [2, 7, 1, 0]# ```def shortest_path_route(start, dest)prev = impl_memo_route(start)res = Array(Int32).newnow : Int32? = dest.to_i32until now.nil?res << now.not_nil!now = prev[now]endres.reverseend# 始点 `start` から最短路木を構築します。## 最短路木は `start` からの最短経路のみを残した全域木です。## ```# route = graph.shortest_path_route(start: 2, dest: 0)# route # => [2, 7, 1, 0]# ```def shortest_path_tree(start, directed : Bool = false) : Array(Array(Int32))dist = [Weight.inf] * @sizedist[start] = Weight.zeronext_node = AtCoder::PriorityQueue({Weight, Int32}).minnext_node << {Weight.zero, start.to_i32}birth = [-1] * @sizeuntil next_node.empty?d, source = next_node.pop.not_nil!next if dist[source] < d@graph[source].each do |e|next_cost = dist[source] + e.weightif next_cost < dist[e.target]dist[e.target] = next_costnext_node << {next_cost, e.target}birth[e.target] = sourceendendendtree = Array.new(@size) { [] of Int32 }@size.times do |target|source = birth[target]next if source == -1tree[source] << targettree[target] << source unless directedendtreeend# 経路復元のための「どこから移動してきたか」を# メモした配列を返します。private def impl_memo_route(start)dist = [Weight.inf] * @sizedist[start] = Weight.zeroprev = Array(Int32?).new(@size) { nil }next_node = AtCoder::PriorityQueue({Weight, Int32}).minnext_node << {Weight.zero, start.to_i32}until next_node.empty?d, source = next_node.pop.not_nil!next if dist[source] < d@graph[source].each do |e|next_cost = dist[source] + e.weightif next_cost < dist[e.target]dist[e.target] = next_costprev[e.target] = sourcenext_node << {next_cost, e.target}endendendprevendendendclass Array(T)def compressb = clone.sort.uniqmap{ |s| b.bsearch_index{ |x| x >= s } || b.size }enddef mappingb = clone.sort.uniqf, g = Hash(Int64, Int64).new, Hash(Int64, Int64).neweach do |s|index = b.bsearch_index{ |x| x >= s } || b.sizef[s] = indexg[index] = send{f, g}endend# .O,# :o.# 'd' :c;. c# lc dKl ;d,.,cl:. oOx.# .x. .,. 'd:.......:ll;. 'lc# .;0; .ol............'col;.# .:do;xl cd'.................,col;.# .,cdd:' od 'x;........:..............':ol;.# ..;lddc,. od od....l:...;x.........,........,lo;# .,:loodl;. .,,kx. .kk:....k,...lo........od.........;.:x,# .,coool:,. ....;lkodl....O:...dk.......;Oo........:x...oo# :dl;'. .lk:...Ok...xkc......xcx.......,k'....:x# ;k, :x:.Olx'.O'd;....;o.O......;Oc......cx# O, . ;xO;.cOO..ll,..l: x,...,dck,.......dc# k: lKd oO. KK .;cld; dc;lOc.;d........,0# dl . cx.cO. .,.KW..x'.........0.# oc .ll;. :k.l: ;l,k,...;:.....0.# o, kkxkOOOOOOOOOkkkkxl:'. ;x.,. .dOoccod:.....cO# x..o. lOxxxxxxxxxxxxxxxxxxkXOOdc' oc .l;,,,;coo:...ol......o0,# O ' xOxxxxxxxxxxxxxxxxxxxxKOxxkOOd; .0. '0:ccc:,,,0ccd;....;lx0l# .x .Okxxxxxxxxxxxxxxxxxxxxx0KxxxxxxkOo. O' do'''''''OllOkoooolckl# ;l .OkxxxxxxxxxxxxxxxxxxxxxxOKxxxxxkOxk0l kkollll0kdoddxkK0Oxllooool.# c: kKxxxxxxxxxxxxxxxxxxxxxxx0XkxxxxkXxxxOO k' ;d. .k,....':ok0dc;.. .'::# o, xO00xxxxxxxxxxxxxxxxxxxxxxKOKxxxxxXdoOk0; .O ;d .k. .cd,ckccc;lx,# d, c0xx0Kkxxxxxxxxxxxxxxxxxxx0O.KkxxxkX. .0K; lk:lOo;;Oo;kd; ' .x;:c .# d, .0KxxxkK0kxxxxxxxxxxxxxxxx0k. l0xxxOx O0 'O::k; .kckO: Okollxxkx. k.# d, xod0xxxxK00OxxxxxxxxxxxxO0l. 'XxxkK' ;K, .Oxxo. .o x: ;O;;xo..K. l:# l; 0:;d0xxxkO.;ok0OkO00OkO0l. KkkKc';d0, ;olxx ,dd; 'Kkkk, 'Oc 'x# :l K:;;o0kxxKc .':c..:o,. O0OlO0Kd. 'ol. :d lO' ;00x;. ck' O.# 'x 0c;;;cO0xkXk, '. cdk00x..cOx ol .od. ,c. 'k; d;# 0. kl;;;;;oO0OK0, ,ccO00KOokk.'x. o: 'cx0; .::c:. od ;d# ;d..xd:;;;;;cdkkk,... ..';llc::,... ;d..xkc .klld. ol ol .k# ,llokkolcccloddkK0K00ck00xodoo:. cl ' .o..d: c. ,k k.# .,:c::;,.. ;d .0;k. ;lodxkKo .d' :x;'.....:xc lc# lx :OOOol 'O :o. dOooodd0. .O# lxc:,k:O .d; ll .dc ld;;;;O' l;# .c, dk:k;.k oOcc,,O. ,x. Oc;;;x: x.# .ld.'lkd;,:cdlc;;0, .:' dxcc:;,'kdllld0;',.. ;loodoool# ,ol. .oo. ...' .:::cccl:. :x. .............';codOc;;;;;;;;# :kd, co .'c, 'k. ,dx:;;;;;;# .:llld;,;:....O' .x: .ko;;;;;;# 'lkcodxdxO. ;x, :kc;;;;;;# ;k;;;;;;dx o0' ;Kd;;;;;n = intskills = (1..n - 1).map { ints }q = intqueries = (1..q).map { ints }graph = Array.new(n) { [] of NgLib::Edge }scc_graph = Array.new(n) { [] of Int64 }skills.each_with_index do |(l, a), i|graph[a - 1] << NgLib::Edge.new(i + 1, l)scc_graph[a - 1] << i + 1endscc = StronglyConnectedComponents.new(scc_graph)# 技 i を覚えるのに必要な最小コストdist = [-OO] * ndist[0] = 0queue = Deque({Int64, Int64}).newqueue << {0_i64, -1_i64}until queue.empty?from, par = queue.popgraph[from].each do |(to, w)|next if to == parchmax(dist[to], Math.max(dist[from], w))queue << {to, from}endendn.times do |i|dist[i] = OO if dist[i] == -OOdist[i] = OO if scc.size(i) >= 2end# 技 i を覚えるための最小コストrmq = NgLib::SparseTable(Int64).max(dist)# レベル x 以下の技は何個?lvs = [] of Int64queries.each do |(t, x)|lvs << x if t == 1endf, g = (dist + lvs).mappingcnt = [0_i64] * f.sizedist.each_with_index do |lv, i|cnt[f[lv]] += 1endcsum = NgLib::StaticRangeSum(Int64).new(cnt)queries.each do |(t, x)|y = xcase twhen 1ans = csum[0..f[x]]puts answhen 2ans = dist[y - 1]puts ans >= OO ? -1 : ansendend