結果

問題 No.1094 木登り / Climbing tree
ユーザー uw_yu1rabbituw_yu1rabbit
提出日時 2021-02-08 18:51:12
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,725 ms / 2,000 ms
コード長 3,652 bytes
コンパイル時間 4,974 ms
コンパイル使用メモリ 148,584 KB
実行使用メモリ 252,788 KB
最終ジャッジ日時 2023-09-19 08:39:12
合計ジャッジ時間 42,850 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1,656 ms
248,444 KB
testcase_02 AC 322 ms
252,788 KB
testcase_03 AC 387 ms
19,468 KB
testcase_04 AC 419 ms
106,416 KB
testcase_05 AC 563 ms
207,448 KB
testcase_06 AC 1,019 ms
84,772 KB
testcase_07 AC 1,693 ms
248,528 KB
testcase_08 AC 1,664 ms
248,444 KB
testcase_09 AC 1,695 ms
248,444 KB
testcase_10 AC 1,694 ms
248,364 KB
testcase_11 AC 1,657 ms
248,548 KB
testcase_12 AC 1,652 ms
248,476 KB
testcase_13 AC 1,678 ms
248,504 KB
testcase_14 AC 1,668 ms
248,520 KB
testcase_15 AC 680 ms
67,948 KB
testcase_16 AC 980 ms
203,472 KB
testcase_17 AC 849 ms
126,056 KB
testcase_18 AC 762 ms
97,172 KB
testcase_19 AC 954 ms
172,448 KB
testcase_20 AC 1,689 ms
248,480 KB
testcase_21 AC 857 ms
134,444 KB
testcase_22 AC 1,725 ms
248,500 KB
testcase_23 AC 1,689 ms
248,576 KB
testcase_24 AC 1,687 ms
248,440 KB
testcase_25 AC 1,677 ms
248,512 KB
testcase_26 AC 1,662 ms
248,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

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

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

    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 {
            if (((self.depth[v] - self.depth[u]) >> i) & 1) > 0 {
                v = self.doubling[i][v].unwrap();
            }
        }
        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].unwrap();
                v = self.doubling[i][v].unwrap();
            }
        }
        self.doubling[0][u].unwrap() as i32
    }

   /* fn length(&mut self,u:usize,v:usize) -> i32 {
        let 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 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