結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2021-08-08 10:07:15 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 240 ms / 5,000 ms |
コード長 | 18,897 bytes |
コンパイル時間 | 16,745 ms |
コンパイル使用メモリ | 295,580 KB |
実行使用メモリ | 24,136 KB |
最終ジャッジ日時 | 2024-09-19 05:53:58 |
合計ジャッジ時間 | 12,676 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
# require "/template"# require "./scanner"# ### Specifications## ```plain# Inside input macro | Expanded code# ----------------------------------------------+---------------------------------------# Uppercase string: Int32, Int64, Float64, etc. | {}.new(Scanner.s)# s | Scanner.s# c | Scanner.c# Other lowercase string: i, i64, f, etc. | Scanner.s.to_{}# operator[]: type[size] | Array.new(input(size)) { input(type) }# Tuple literal: {t1, t2, t3} | {input(t1), input(t2), input(t3)}# Array literal: [t1, t2, t3] | [input(t1), input(t2), input(t3)]# Range literal: t1..t2 | input(t1)..input(t2)# If: cond ? t1 : t2 | cond ? input(t1) : input(t2)# Assign: target = value | target = input(value)# ```## ### Examples## Input:# ```plain# 5 3# foo bar# 1 2 3 4 5# ```# ```# n, m = input(Int32, Int64) # => {5, 10i64}# input(String, Char[m]) # => {"foo", ['b', 'a', 'r']}# input(Int32[n]) # => [1, 2, 3, 4, 5]# ```# ```# n, m = input(i, i64) # => {5, 10i64}# input(s, c[m]) # => {"foo", ['b', 'a', 'r']}# input(i[n]) # => [1, 2, 3, 4, 5]# ```## Input:# ```plain# 2 3# 1 2 3# 4 5 6# ```## ```# h, w = input(i, i) # => {2, 3}# input(i[h, w]) # => [[1, 2, 3], [4, 5, 6]]# ```# ```# input(i[i][i]) # => [[1, 2, 3], [4, 5, 6]]# ```## Input:# ```plain# 5 3# 3 1 4 2 5# 1 2# 2 3# 3 1# ```# ```# n, m = input(i, i) # => {5, 3}# input(i.pred[n]) # => [2, 0, 3, 1, 4]# input({i - 1, i - 1}[m]) # => [{0, 1}, {1, 2}, {2, 0}]# ```## Input:# ```plain# 3# 1 2# 2 2# 3 2# ```# ```# input({tmp = i, tmp == 1 ? i : i.pred}[i]) # => [{1, 2}, {2, 1}, {3, 1}]# ```## Input:# ```plain# 3# 1 2# 2 3# 3 1# ```# ```# n = input(i)# input_column({Int32, Int32}, n) # => {[1, 2, 3], [2, 3, 1]}# ```class Scannerprivate def self.skip_to_not_spacepeek = STDIN.peeknot_space = peek.index { |x| x != 32 && x != 10 } || peek.sizeSTDIN.skip(not_space)enddef self.cskip_to_not_spaceSTDIN.read_char.not_nil!enddef self.sskip_to_not_spacepeek = STDIN.peekif index = peek.index { |x| x == 32 || x == 10 }STDIN.skip(index + 1)return String.new(peek[0, index])endString.build do |buffer|loop dobuffer.write peekSTDIN.skip(peek.size)peek = STDIN.peekbreak if peek.empty?if index = peek.index { |x| x == 32 || x == 10 }buffer.write peek[0, index]STDIN.skip(index)breakendendendendendmacro internal_input(type, else_ast){% if Scanner.class.has_method?(type.id) %}Scanner.{{type.id}}{% elsif type.stringify == "String" %}Scanner.s{% elsif type.stringify == "Char" %}Scanner.c{% elsif type.stringify =~ /[A-Z][a-z0-9_]*/ %}{{type.id}}.new(Scanner.s){% elsif String.has_method?("to_#{type}".id) %}Scanner.s.to_{{type.id}}{% else %}{{else_ast}}{% end %}endmacro internal_input_array(type, args){% for i in 0...args.size %}%size{i} = input({{args[i]}}){% end %}{% begin %}{% for i in 0...args.size %} Array.new(%size{i}) { {% end %}input({{type.id}}){% for i in 0...args.size %} } {% end %}{% end %}endmacro input(type){% if type.is_a?(Call) %}{% if type.receiver.is_a?(Nop) %}internal_input({{type.name}}, {{type.name}}({% for argument in type.args %} input({{argument}}), {% end %})){% elsif type.name.stringify == "[]" %}internal_input_array({{type.receiver}}, {{type.args}}){% else %}input({{type.receiver}}).{{type.name.id}}({% for argument in type.args %} input({{argument}}), {% end %}) {{type.block}}{% end %}{% elsif type.is_a?(TupleLiteral) %}{ {% for i in 0...type.size %} input({{type[i]}}), {% end %} }{% elsif type.is_a?(ArrayLiteral) %}[ {% for i in 0...type.size %} input({{type[i]}}), {% end %} ]{% elsif type.is_a?(RangeLiteral) %}Range.new(input({{type.begin}}), input({{type.end}}), {{type.excludes_end?}}){% elsif type.is_a?(If) %}{{type.cond}} ? input({{type.then}}) : input({{type.else}}){% elsif type.is_a?(Assign) %}{{type.target}} = input({{type.value}}){% else %}internal_input({{type.id}}, {{type.id}}){% end %}endmacro input(*types){ {% for type in types %} input({{type}}), {% end %} }endmacro input_column(types, size){% for type, i in types %}%array{i} = Array({{type}}).new({{size}}){% end %}{{size}}.times do{% for type, i in types %}%array{i} << input({{type}}){% end %}end{ {% for type, i in types %} %array{i}, {% end %} }end# require "./tuple/times"struct Tupledef times(&block) : Nil{% begin %}{% for i in 0...@type.size %}{% if @type[i].has_method?(:each) %}self[{{i}}].each do |i{{i}}|{% else %}self[{{i}}].times do |i{{i}}|{% end %}{% end %}yield({% for i in 0...@type.size %} i{{i}}, {% end %}){% for i in 0...@type.size %} end {% end %}{% end %}endprivate class TimesIterator(T)include Iterator(T)def initialize(@n : T)tuple = {% begin %}{ {% for i in 0...T.size %} T[{{i}}].zero, {% end %} }{% end %}@index = tuple.as(T)@first = trueenddef nextif @first@first = falsereturn @indexend{% begin %}{%type = @type.type_vars[0]size = type.size%}{% for i in 1..size %}if @index[{{size - i}}] < @n[{{size - i}}] - 1@index = {{% for j in 0...size %}{% if j < size - i %}@index[{{j}}],{% elsif j == size - i %}@index[{{j}}] + 1,{% else %}{{type[j]}}.zero,{% end %}{% end %}}return @indexend{% end %}stop{% end %}endenddef timesTimesIterator(self).new(self)endend# require "./comparable/min_max"module Comparable(T)def min(x : T)self > x ? x : selfenddef max(x : T)self < x ? x : selfendend# require "./array/new"class Arraydef self.new(sizes : Tuple(*T), initial_value) forall T{% begin %}{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { {% end %}initial_value{% for i in 0...T.size %} } {% end %}{% end %}enddef self.new(sizes : Tuple(*T), &block) forall T{% begin %}{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { |%i{i}| {% end %}yield({% for i in 0...T.size %} %i{i}, {% end %}){% for i in 0...T.size %} } {% end %}{% end %}endend# require "./array/change"class Array(T)def chmin(i : Int, value : T)(self[i] > value).tap do |f|self[i] = value if fendendprotected def chmin(i : Int, *indexes, value)self[i].chmin(*indexes, value: value)enddef chmin(indexes : Tuple, value)chmin(*indexes, value: value)enddef chmax(i : Int, value : T)(self[i] < value).tap do |f|self[i] = value if fendendprotected def chmax(i : Int, *indexes, value)self[i].chmax(*indexes, value: value)enddef chmax(indexes : Tuple, value)chmax(*indexes, value: value)endend# require "/graph/euler_tour_for_vertex"# require "../graph"# require "./graph/edge"struct WeightedEdge(T)include Comparable(WeightedEdge(T))property to : Int32, cost : Tdef initialize(@to, @cost : T)enddef <=>(other : WeightedEdge(T)){cost, to} <=> {other.cost, other.to}enddef to_s(io) : Nilio << '(' << to << ", " << cost << ')'enddef inspect(io) : Nilio << "->#{to}(#{cost})"endendstruct WeightedEdge2(T)include Comparable(WeightedEdge2(T))property from : Int32, to : Int32, cost : Tdef initialize(@from, @to, @cost : T)enddef initialize(@from, edge : WeightedEdge(T))@to, @cost = edge.to, edge.costenddef <=>(other : WeightedEdge2(T)){cost, from, to} <=> {other.cost, other.from, other.to}enddef reverseWeightedEdge2(T).new(to, from, cost)enddef sortWeightedEdge2(T).new(*{to, from}.minmax, cost)enddef to_s(io) : Nilio << '(' << from << ", " << to << ", " << cost << ')'enddef inspect(io) : Nilio << from << "->" << to << '(' << cost << ')'endendstruct UnweightedEdgeproperty to : Int32def initialize(@to)enddef initialize(@to, cost)enddef cost1enddef to_s(io) : Nilio << toenddef inspect(io) : Nilio << "->" << toendendstruct UnweightedEdge2property from : Int32, to : Int32def initialize(@from, @to)enddef initialize(@from, @to, cost)enddef initialize(@from, edge : UnweightedEdge)@to = edge.toenddef cost1enddef reverseUnweightedEdge2.new(to, from)enddef sortUnweightedEdge2.new(*{to, from}.minmax)enddef to_s(io) : Nilio << '(' << from << ", " << to << ')'enddef inspect(io) : Nilio << from << "->" << toendendmodule Graph(Edge, Edge2)include Enumerable(Edge2)getter graph : Array(Array(Edge))def initialize(size : Int)@graph = Array(Array(Edge)).new(size) { [] of Edge }enddef initialize(size : Int, edges : Enumerable)initialize(size)add_edges(edges)end# Add *edge*.abstract def <<(edge : Edge2)# :ditto:def <<(edge : Tuple)self << Edge2.new(*edge)enddef add_edges(edges : Enumerable)edges.each { |edge| self << edge }enddelegate size, to: @graphdelegate :[], to: @graph# Yields each edge of the graph, ans returns `nil`.def each(&) : Nil(0...size).each do |v|self[v].each do |edge|yield Edge2.new(v, edge)endendenddef reverseif self.class.directed?each_with_object(self.class.new(size)) do |edge, reversed|reversed << edge.reverseendelsedupendenddef to_undirectedif self.class.directed?each_with_object(self.class.new(size)) do |edge, graph|graph << edgegraph << edge.reverse if self.class.directed?endelsedupendenddef to_s(io : IO) : Nilio << '['join(", ", io) do |edge, io|edge.inspect ioendio << ']'enddef inspect(io : IO) : Nilio << "[\n"graph.each do |edges|io << " " << edges << ",\n"endio << ']'endendclass DirectedGraph(T)include Graph(WeightedEdge(T), WeightedEdge2(T))def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))superenddef initialize(size : Int, edges : Enumerable({Int32, Int32, T}))superenddef <<(edge : WeightedEdge2(T))raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)selfenddef self.weighted?trueenddef self.directed?trueendendclass UndirectedGraph(T)include Graph(WeightedEdge(T), WeightedEdge2(T))def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))superenddef initialize(size : Int, edges : Enumerable({Int32, Int32, T}))superenddef <<(edge : WeightedEdge2(T))raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)@graph[edge.to] << WeightedEdge.new(edge.from, edge.cost)selfenddef self.weighted?trueenddef self.directed?falseendendclass UnweightedDirectedGraphinclude Graph(UnweightedEdge, UnweightedEdge2)def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable)superenddef <<(edge : UnweightedEdge2)raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << UnweightedEdge.new(edge.to)selfenddef self.weighted?falseenddef self.directed?trueendendclass UnweightedUndirectedGraphinclude Graph(UnweightedEdge, UnweightedEdge2)def initialize(size : Int)superenddef initialize(size : Int, edges : Enumerable)superenddef <<(edge : UnweightedEdge2)raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size@graph[edge.from] << UnweightedEdge.new(edge.to)@graph[edge.to] << UnweightedEdge.new(edge.from)selfenddef each_child(vertex : Int, parent, &block) : Nilgraph[vertex].each do |u|yield u if u != parentendenddef each_child(vertex : Int, parent)graph[vertex].each.select { |u| u != parent }enddef self.weighted?falseenddef self.directed?falseendendclass EulerTourForVertexgetter graph : UnweightedUndirectedGraphdef initialize(@graph)@ls = Array(Int32).new(size, 0)@rs = Array(Int32).new(size, 0)@k = 0enddelegate size, to: @graphdelegate :[], to: @graphdelegate add_edge, to: @graphdef dfs(v : Int, p : Int) : Nil@ls[v] = @k@k += 1@graph[v].each do |edge|dfs(edge.to, v) if edge.to != pend@rs[v] = @kenddef run(root : Int)dfs(root, -1){@ls, @rs}endend# require "atcoder/SegTree"# ac-library.cr by hakatashi https://github.com/google/ac-library.cr## Copyright 2021 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 [atcoder::segtree](https://atcoder.github.io/ac-library/master/document_en/segtree.html).## The identity element will be implicitly defined as nil, so you don't# have to manually define it. In the other words, you cannot include# nil into an element of the monoid.## ```# tree = AtCoder::SegTree.new((0...100).to_a) { |a, b| [a, b].min }# tree[10...50] # => 10# ```class SegTree(T)property values : Array(T)def initialize(values : Array(T))initialize(values) { |a, b| a > b ? a : b }enddef initialize(values : Array(T), &@operator : T, T -> T)@values = values@segments = Array(T | Nil).new(2 ** ::Math.log2(values.size).ceil.to_i - 1, nil)# initialize segments(@segments.size - 1).downto(0) do |i|child1 = nil.as(T | Nil)child2 = nil.as(T | Nil)if i * 2 + 1 < @segments.sizechild1 = @segments[i * 2 + 1]child2 = @segments[i * 2 + 2]elseif i * 2 + 1 - @segments.size < @values.sizechild1 = @values[i * 2 + 1 - @segments.size]endif i * 2 + 2 - @segments.size < @values.sizechild2 = @values[i * 2 + 2 - @segments.size]endend@segments[i] = operate(child1, child2)endend@[AlwaysInline]private def operate(a : T | Nil, b : T | Nil)if a.nil?belsif b.nil?aelse@operator.call(a, b)endend# Implements atcoder::segtree.set(index, value)def []=(index : Int, value : T)@values[index] = valueparent_index = (index + @segments.size - 1) // 2while parent_index >= 0i = parent_indexchild1 = nil.as(T | Nil)child2 = nil.as(T | Nil)if i * 2 + 1 < @segments.sizechild1 = @segments[i * 2 + 1]child2 = @segments[i * 2 + 2]elseif i * 2 + 1 - @segments.size < @values.sizechild1 = @values[i * 2 + 1 - @segments.size]endif i * 2 + 2 - @segments.size < @values.sizechild2 = @values[i * 2 + 2 - @segments.size]endend@segments[i] = operate(child1, child2)parent_index = (parent_index - 1) // 2endend# Implements atcoder::segtree.get(index)def [](index : Int)@values[index]end# Implements atcoder::segtree.prod(l, r)def [](range : Range(Int, Int))a = range.beginb = range.exclusive? ? range.end : range.end + 1get_value(a, b, 0, 0...(@segments.size + 1)).not_nil!enddef get_value(a : Int, b : Int, segment_index : Int, range : Range(Int, Int))if range.end <= a || b <= range.beginreturn nilendif a <= range.begin && range.end <= bif segment_index < @segments.sizereturn @segments[segment_index]elsereturn @values[segment_index - @segments.size]endendrange_median = (range.begin + range.end) // 2child1 = get_value(a, b, 2 * segment_index + 1, range.begin...range_median)child2 = get_value(a, b, 2 * segment_index + 2, range_median...range.end)operate(child1, child2)end# compatibility with ac-library# Implements atcoder::segtree.set(index, value)# alias of `.[]=`def set(index : Int, value : T)self.[]=(index, value)end# Implements atcoder::segtree.get(index)# alias of `.[]`def get(index : Int)self.[](index)end# Implements atcoder::segtree.prod(left, right)def prod(left : Int, right : Int)self.[](left...right)end# Implements atcoder::segtree.all_prod(l, r)def all_prodself.[](0...@values.size)end# FIXME: Unimplementeddef max_rightraise NotImplementedError.newend# FIXME: Unimplementeddef max_leftraise NotImplementedError.newendendendn, q = input(i, i)c = input(i64[n])graph = UnweightedUndirectedGraph.new n, input({i - 1, i - 1}[n - 1])euler = EulerTourForVertex.new(graph)ls, rs = euler.run(0)seg = AtCoder::SegTree.new([0i64] * n) { |x, y| x ^ y }ls.each_with_index { |x, i| seg[x] = c[i] }q.times dot, x, y = input(i, i - 1, i)case twhen 1seg[ls[x]] ^= ywhen 2puts seg[ls[x]...rs[x]]endend