結果

問題 No.1094 木登り / Climbing tree
ユーザー uw_yu1rabbit
提出日時 2021-02-08 17:57:05
言語 Rust
(1.83.0 + proconio)
結果
RE  
実行時間 -
コード長 3,734 bytes
コンパイル時間 11,914 ms
コンパイル使用メモリ 377,432 KB
実行使用メモリ 102,016 KB
最終ジャッジ日時 2024-07-05 19:46:55
合計ジャッジ時間 22,209 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> src/main.rs:15:13
   |
15 |         let mut dep:Vec<i32> = vec![0;_n];
   |             ----^^^
   |             |
   |             help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
  --> src/main.rs:16:13
   |
16 |         let mut c:Vec<i32> = vec![0;_n];
   |             ----^
   |             |
   |             help: remove this `mut`

warning: variable does not need to be mutable
  --> src/main.rs:17:13
   |
17 |         let mut C:Vec<Vec<i32>> = vec![vec![];_n];
   |             ----^
   |             |
   |             help: remove this `mut`

warning: variable does not need to be mutable
  --> src/main.rs:19:13
   |
19 |         let mut digit:usize = 64;
   |             ----^^^^^
   |             |
   |             help: remove this `mut`

warning: variable does not need to be mutable
  --> src/main.rs:20:13
   |
20 |         let mut doub:Vec<Vec<i32>> = vec![vec![-1;_n];digit];
   |             ----^^^^
   |             |
   |             help: remove this `mut`

warning: variable does not need to be mutable
  --> src/main.rs:85:13
   |
85 |         let mut f = self.answer_to_query(u,v) as usize;
   |             ----^
   |             |
   |             help: remove this `mut`

warning: variable does not need to be mutable
  --> src/main.rs:90:13
   |
90 |         let mut f = self.answer_to_query(u,v) as usize;
   |             ----^
   |             |
   |             help: remove this `mut`

warning: field `n` is never read
 --> src/main.rs:8:5
  |
3 | struct LCA{
  |        --- field in this struct
...
8 |     n:usize,
  |     ^
  |
  = note: `#[warn(dead_code)]` on by default

warning: methods `length` and `is_on_path` are never used
  --> src/main.rs:84:8
   |
13 | impl LCA{
   | -------- methods in this implementation
...
84 |     fn length(&mut self,u:usize,v:usize) -> i32 {
   |        ^^^^^^
...
94 |     fn is_on_path(&mut s

ソースコード

diff # 

use std::io::*;
use std::str::FromStr;
struct LCA{
    depth:Vec<i32>,
    dig:i32,
    cost:Vec<Vec<i32>>,
    costs:Vec<i32>,
    n:usize,
    g:Vec<Vec<i32>>,
    doubling:Vec<Vec<i32>>
}

impl LCA{
    fn new(_n:usize) -> Self{
        let mut dep:Vec<i32> = vec![0;_n];
        let mut c:Vec<i32> = vec![0;_n];
        let mut C:Vec<Vec<i32>> = vec![vec![];_n];
        let mut _g:Vec<Vec<i32>> = vec![vec![];_n];
        let mut digit:usize = 64;
        let mut doub:Vec<Vec<i32>> = vec![vec![-1;_n];digit];
        LCA{
            depth:dep,
            costs:c,
            cost:C,
            doubling:doub,
            n:_n,
            dig:digit as i32,
            g:_g
        }
    }

    fn addedge(&mut self,u:usize,v:usize,c:i32){//コスト指定がなければc = 0を渡す
        self.g[u].push(v as i32);
        self.g[v].push(u as i32);
        self.cost[u].push(c);
        self.cost[v].push(c);
    }

    fn dfs(&mut self,now:usize,par:i32,d:i32,c:i32){
        self.doubling[0][now] = par;
        self.depth[now] = d;
        self.costs[now] = c;
        for i in 0..self.g[now].len(){
            if self.g[now][i] != par {
                self.dfs(self.g[now][i] as usize,now as i32,d + 1, c + self.cost[now][i]);
            }
        }
    }

    fn construct(&mut self){
        self.dfs(0,-1,0,0);
        for i in 0..(self.dig as usize - 1){
            for j in 0..self.doubling[i].len(){
                if self.doubling[i][j] == -1{
                    self.doubling[i + 1][j] = -1;
                } else {
                    self.doubling[i + 1][j] = self.doubling[i][self.doubling[i][j] as usize];
                }
            }
        }
    }

    fn answer_to_query(&mut self, mut u:usize,mut v:usize) -> i32{
        if self.depth[u] > self.depth[v] {
            std::mem::swap(&mut u,&mut v);
        }
        for i in (0..self.dig as usize).rev(){
            if ((self.depth[v] - self.depth[u]) >> i) & 1 == 0{
                v = self.doubling[i][v] as usize;
            }
        }
        if u == v {
           return u as i32;
        }
        for i in (0..self.dig as usize).rev(){
            if self.doubling[i][u] != self.doubling[i][v]{
                u = self.doubling[i][u] as usize;
                v = self.doubling[i][v] as usize;
            }
        }
        self.doubling[0][u]
    }

    fn length(&mut self,u:usize,v:usize) -> i32 {
        let mut f = self.answer_to_query(u,v) as usize;
        self.depth[u] + self.depth[v] - 2 * self.depth[f]
    }

    fn dist(&mut self, u:usize,v:usize)-> i32 {
        let mut f = self.answer_to_query(u,v) as usize;
        self.costs[u] + self.costs[v] - 2 * self.costs[f]
    }
    
    fn is_on_path(&mut self,u:usize,v:usize,x:usize) -> bool {
        self.length(u,x) + self.length(v,x) == self.length(u,v)
    }
}
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
fn main(){
    let n:usize = read();
    let mut abc:Vec<Vec<i32>> = vec![vec![0;3];n];
    let mut lca = LCA::new(n);
    for i in 0..n - 1{
        abc[i] = (0..3).map(|_| read()).collect();
        lca.addedge(abc[i][0] as usize - 1, abc[i][1] as usize - 1, abc[i][2]);
    }
    lca.construct();
   let q:usize = read();
    let mut _q:Vec<Vec<usize>> = vec![vec![0;2];q];
    for i in 0..q{
        _q[i] = (0..2).map(|_| read()).collect();
    }
    for i in 0..q{
       println!("{}",lca.dist(_q[i][0] - 1,_q[i][1] - 1));
    }
}
0