結果

問題 No.1094 木登り / Climbing tree
ユーザー uw_yu1rabbituw_yu1rabbit
提出日時 2021-02-08 18:51:12
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,819 ms / 2,000 ms
コード長 3,652 bytes
コンパイル時間 19,471 ms
コンパイル使用メモリ 387,992 KB
実行使用メモリ 255,916 KB
最終ジャッジ日時 2024-07-05 20:27:59
合計ジャッジ時間 56,366 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1,733 ms
248,412 KB
testcase_02 AC 293 ms
255,916 KB
testcase_03 AC 357 ms
19,456 KB
testcase_04 AC 397 ms
106,496 KB
testcase_05 AC 548 ms
207,544 KB
testcase_06 AC 914 ms
84,864 KB
testcase_07 AC 1,667 ms
248,448 KB
testcase_08 AC 1,756 ms
248,432 KB
testcase_09 AC 1,728 ms
248,432 KB
testcase_10 AC 1,707 ms
248,296 KB
testcase_11 AC 1,684 ms
248,412 KB
testcase_12 AC 1,670 ms
248,496 KB
testcase_13 AC 1,696 ms
248,292 KB
testcase_14 AC 1,724 ms
248,480 KB
testcase_15 AC 613 ms
68,608 KB
testcase_16 AC 875 ms
205,696 KB
testcase_17 AC 729 ms
127,452 KB
testcase_18 AC 673 ms
98,108 KB
testcase_19 AC 815 ms
174,280 KB
testcase_20 AC 1,783 ms
248,440 KB
testcase_21 AC 741 ms
135,936 KB
testcase_22 AC 1,819 ms
248,448 KB
testcase_23 AC 1,741 ms
248,336 KB
testcase_24 AC 1,716 ms
248,520 KB
testcase_25 AC 1,710 ms
248,508 KB
testcase_26 AC 1,717 ms
248,344 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