結果
問題 | No.1637 Easy Tree Query |
ユーザー | akiradeveloper |
提出日時 | 2021-08-06 21:30:43 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 12,389 bytes |
コンパイル時間 | 6,019 ms |
コンパイル使用メモリ | 193,704 KB |
実行使用メモリ | 30,204 KB |
最終ジャッジ日時 | 2023-10-17 04:58:03 |
合計ジャッジ時間 | 9,659 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 54 ms
17,212 KB |
testcase_03 | AC | 1 ms
4,348 KB |
testcase_04 | AC | 30 ms
8,796 KB |
testcase_05 | AC | 35 ms
7,828 KB |
testcase_06 | AC | 25 ms
6,204 KB |
testcase_07 | AC | 7 ms
4,348 KB |
testcase_08 | AC | 23 ms
7,024 KB |
testcase_09 | AC | 50 ms
12,632 KB |
testcase_10 | AC | 19 ms
5,116 KB |
testcase_11 | AC | 66 ms
14,436 KB |
testcase_12 | AC | 51 ms
11,680 KB |
testcase_13 | AC | 14 ms
4,596 KB |
testcase_14 | AC | 50 ms
12,612 KB |
testcase_15 | AC | 68 ms
14,980 KB |
testcase_16 | AC | 74 ms
15,768 KB |
testcase_17 | AC | 16 ms
4,952 KB |
testcase_18 | AC | 32 ms
7,756 KB |
testcase_19 | AC | 36 ms
8,892 KB |
testcase_20 | AC | 49 ms
11,696 KB |
testcase_21 | AC | 34 ms
9,268 KB |
testcase_22 | AC | 75 ms
16,912 KB |
testcase_23 | AC | 18 ms
5,532 KB |
testcase_24 | AC | 36 ms
9,176 KB |
testcase_25 | AC | 34 ms
7,616 KB |
testcase_26 | AC | 53 ms
12,464 KB |
testcase_27 | AC | 75 ms
16,356 KB |
testcase_28 | AC | 28 ms
6,600 KB |
testcase_29 | AC | 50 ms
10,956 KB |
testcase_30 | AC | 37 ms
9,508 KB |
testcase_31 | AC | 14 ms
4,348 KB |
testcase_32 | AC | 24 ms
6,696 KB |
testcase_33 | AC | 27 ms
5,948 KB |
testcase_34 | AC | 51 ms
30,204 KB |
コンパイルメッセージ
warning: field `n` is never read --> Main.rs:141:5 | 140 | struct HLDecomposition { | --------------- field in this struct 141 | n: usize, | ^ | = note: `#[warn(dead_code)]` on by default warning: methods `lca`, `vertex_decomposition`, `edge_decomposition`, `vertex_decomposition_between`, `edge_decomposition_between`, and `distance` are never used --> Main.rs:243:12 | 151 | impl HLDecomposition { | -------------------- methods in this implementation ... 243 | pub fn lca(&self, u: usize, v: usize) -> usize { | ^^^ ... 257 | pub fn vertex_decomposition(&self) -> Vec<(usize, usize)> { | ^^^^^^^^^^^^^^^^^^^^ ... 273 | pub fn edge_decomposition(&self) -> Vec<(usize, usize)> { | ^^^^^^^^^^^^^^^^^^ ... 282 | pub fn vertex_decomposition_between(&self, u: usize, v: usize) -> Vec<(usize, usize)> { | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ... 303 | pub fn edge_decomposition_between(&self, u: usize, v: usize) -> Vec<(usize, usize)> { | ^^^^^^^^^^^^^^^^^^^^^^^^^^ ... 325 | pub fn distance(&self, u: usize, v: usize) -> usize { | ^^^^^^^^ warning: unused `Result` that must be used --> Main.rs:130:9 | 130 | writeln!(out,"{}",sum); | ^^^^^^^^^^^^^^^^^^^^^^ | = note: this `Result` may be an `Err` variant, which should be handled = note: `#[warn(unused_must_use)]` on by default = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info) warning: variable `V` should have a snake case name --> Main.rs:274:13 | 274 | let V = self.vertex_decomposition(); | ^ help: convert the identifier to snake case (notice the capitalization): `v` | = note: `#[warn(non_snake_case)]` on by default warning: 4 warnings emitted
ソースコード
#[doc = " https://github.com/akiradeveloper/rust-comp-snippets"] #[allow(unused_imports)] use std::cmp::{max, min, Ordering}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::iter::FromIterator; #[macro_export] macro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; } #[macro_export] macro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; } #[macro_export] macro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; } #[macro_export] macro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; } #[macro_export] macro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; } #[macro_export] macro_rules ! cfor { ( ; $ ( $ rest : tt ) * ) => { cfor ! ( ( ) ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; ; $ ( $ rest : tt ) * ) => { cfor ! ( $ ( $ init ) ,+; ! false ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; ; $ body : block ) => { cfor ! { $ ( $ init ) ,+; $ cond ; ( ) ; $ body } } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; $ ( $ step : expr ) ,+; $ body : block ) => { { $ ( $ init ; ) + while $ cond { let mut _first = true ; let mut _continue = false ; loop { if ! _first { _continue = true ; break } _first = false ; $ body } if ! _continue { break } $ ( $ step ; ) + } } } ; } #[doc = " main"] #[allow(unused_imports)] use std::io::{stdin, stdout, BufWriter, Write}; #[macro_export] macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; } #[macro_export] macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; } #[macro_export] macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; } use std::io; use std::io::BufRead; use std::str; pub struct Parser<R> { reader: R, buf: Vec<u8>, pos: usize, } impl Parser<io::Empty> { pub fn from_str(s: &str) -> Parser<io::Empty> { Parser { reader: io::empty(), buf: s.as_bytes().to_vec(), pos: 0, } } } impl<R: BufRead> Parser<R> { pub fn new(reader: R) -> Parser<R> { Parser { reader: reader, buf: vec![], pos: 0, } } pub fn update_buf(&mut self) { self.buf.clear(); self.pos = 0; loop { let (len, complete) = { let buf2 = self.reader.fill_buf().unwrap(); self.buf.extend_from_slice(buf2); let len = buf2.len(); if len == 0 { break; } (len, buf2[len - 1] <= 0x20) }; self.reader.consume(len); if complete { break; } } } pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } let mut end = begin; while end < self.buf.len() && (self.buf[end] > 0x20) { end += 1; } if begin != self.buf.len() { self.pos = end; return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>(); } else { self.update_buf(); } } } } #[allow(unused_macros)] macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } } #[doc = " https://github.com/hatoo/competitive-rust-snippets"] const BIG_STACK_SIZE: bool = true; #[allow(dead_code)] fn main() { use std::thread; if BIG_STACK_SIZE { thread::Builder::new() .stack_size(32 * 1024 * 1024) .name("solve".into()) .spawn(solve) .unwrap() .join() .unwrap(); } else { solve(); } } fn solve() { let out = stdout(); let mut out = BufWriter::new(out.lock()); input!{ n:usize,q:usize, ab:[(usize,usize);n-1], px:[(usize,u64);q], } let mut t = HLDecomposition::new(n); for (a,b) in ab { t.connect(a-1, b-1); } t.build(0); // dbg!(&t.subcnt); let mut sum = 0; for (p,x) in px { let m = t.subcnt[p-1]; sum += m as u64 * x; writeln!(out,"{}",sum); } } #[doc = " HL分解は、木構造をパスの集合に分解する。"] #[doc = " こうして木構造をvid木上で一直線状にすることにより、"] #[doc = " セグツリーなどの配列構造に対するアルゴリズムを適用可能になる。"] #[doc = " そして、頂点や辺にvidをつける。ここで辺は子ノードの頂点vidで表される。"] #[doc = " クエリ(u,v)に対して、木上のパスに含まれるパス集合(vidベース)を列挙する。"] #[doc = " "] #[doc = " 構築 O(N)"] struct HLDecomposition { n: usize, g: Vec<Vec<usize>>, subcnt: Vec<usize>, depth: Vec<usize>, pub par: Vec<Option<usize>>, heavy_next: Vec<Option<usize>>, heavy_head: Vec<usize>, real_to_virt: Vec<usize>, pub virt_to_real: Vec<usize>, } impl HLDecomposition { pub fn new(n: usize) -> Self { HLDecomposition { n: n, g: vec![vec![]; n], subcnt: vec![0; n], depth: vec![0; n], par: vec![None; n], heavy_next: vec![None; n], heavy_head: vec![n; n], real_to_virt: vec![n; n], virt_to_real: vec![n; n], } } pub fn connect(&mut self, u: usize, v: usize) { self.g[u].push(v); self.g[v].push(u); } #[doc = " O(N)"] pub fn build(&mut self, root: usize) { self.dfs1(root); self.dfs2(root); self.bfs(root); } fn dfs1(&mut self, root: usize) { self.depth[root] = 0; self.par[root] = None; self.dfs1_sub(root, None); } fn dfs1_sub(&mut self, u: usize, par: Option<usize>) -> usize { let mut cnt = 1; for v in self.g[u].clone() { if Some(v) == par { continue; } self.depth[v] = self.depth[u] + 1; self.par[v] = Some(u); cnt += self.dfs1_sub(v, Some(u)); } self.subcnt[u] = cnt; cnt } fn dfs2(&mut self, root: usize) { self.dfs2_sub(root, None); } fn dfs2_sub(&mut self, u: usize, par: Option<usize>) { let mut maxv = 0; let mut heavy_next = None; let cld = self.g[u].clone(); for &v in &cld { if Some(v) == par { continue; } if self.subcnt[v] > maxv { maxv = self.subcnt[v]; heavy_next = Some(v); } } if let Some(hn) = heavy_next { self.heavy_next[u] = Some(hn); self.dfs2_sub(hn, Some(u)); } for &v in &cld { if Some(v) == par || Some(v) == heavy_next { continue; } self.dfs2_sub(v, Some(u)); } } fn bfs(&mut self, root: usize) { let mut cur_virt_id = 0; let mut q = VecDeque::new(); q.push_back(root); while let Some(h) = q.pop_front() { let mut cur0 = Some(h); while cur0.is_some() { let cur = cur0.unwrap(); self.real_to_virt[cur] = cur_virt_id; self.virt_to_real[cur_virt_id] = cur; cur_virt_id += 1; self.heavy_head[cur] = h; for v in self.g[cur].clone() { if Some(v) == self.par[cur] || Some(v) == self.heavy_next[cur] { continue; } q.push_back(v); } cur0 = self.heavy_next[cur]; } } } #[doc = " O(log N)"] pub fn lca(&self, u: usize, v: usize) -> usize { let mut l = u; let mut r = v; loop { if self.real_to_virt[l] > self.real_to_virt[r] { std::mem::swap(&mut l, &mut r); } if self.heavy_head[l] == self.heavy_head[r] { return l; } r = self.par[self.heavy_head[r]].unwrap(); } } #[doc = " O(N)"] pub fn vertex_decomposition(&self) -> Vec<(usize, usize)> { let mut vhead = vec![self.n; self.n]; for i in 0..self.n { vhead[i] = self.real_to_virt[self.heavy_head[i]]; } let mut hs = std::collections::HashMap::new(); for x in vhead { *hs.entry(x).or_insert(0) += 1; } let mut res = vec![]; for (k, v) in hs { res.push((k, k + v - 1)); } res } #[doc = " O(N)"] pub fn edge_decomposition(&self) -> Vec<(usize, usize)> { let V = self.vertex_decomposition(); let mut res = vec![]; for (u, v) in V { let u = if u == 0 { 1 } else { u }; res.push((u, v)); } res } pub fn vertex_decomposition_between(&self, u: usize, v: usize) -> Vec<(usize, usize)> { let mut res = vec![]; let mut l = u; let mut r = v; loop { if self.real_to_virt[l] > self.real_to_virt[r] { std::mem::swap(&mut l, &mut r); } let p = ( std::cmp::max(self.real_to_virt[self.heavy_head[r]], self.real_to_virt[l]), self.real_to_virt[r], ); res.push(p); if self.heavy_head[l] != self.heavy_head[r] { r = self.par[self.heavy_head[r]].unwrap(); } else { break; } } res } pub fn edge_decomposition_between(&self, u: usize, v: usize) -> Vec<(usize, usize)> { let mut res = vec![]; let mut l = u; let mut r = v; loop { if self.real_to_virt[l] > self.real_to_virt[r] { std::mem::swap(&mut l, &mut r); } if self.heavy_head[l] != self.heavy_head[r] { let p = (self.real_to_virt[self.heavy_head[r]], self.real_to_virt[r]); res.push(p); r = self.par[self.heavy_head[r]].unwrap(); } else { if l != r { let p = (self.real_to_virt[l] + 1, self.real_to_virt[r]); res.push(p); } break; } } res } pub fn distance(&self, u: usize, v: usize) -> usize { self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)] } }