結果

問題 No.898 tri-βutree
ユーザー phsplsphspls
提出日時 2023-01-03 20:50:22
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 800 ms / 4,000 ms
コード長 4,585 bytes
コンパイル時間 13,012 ms
コンパイル使用メモリ 390,176 KB
実行使用メモリ 45,720 KB
最終ジャッジ日時 2024-11-27 02:24:06
合計ジャッジ時間 28,623 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 234 ms
45,720 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 788 ms
41,308 KB
testcase_08 AC 732 ms
41,440 KB
testcase_09 AC 738 ms
41,300 KB
testcase_10 AC 783 ms
41,236 KB
testcase_11 AC 752 ms
41,300 KB
testcase_12 AC 777 ms
42,192 KB
testcase_13 AC 743 ms
42,200 KB
testcase_14 AC 743 ms
41,300 KB
testcase_15 AC 758 ms
41,296 KB
testcase_16 AC 788 ms
41,424 KB
testcase_17 AC 800 ms
42,196 KB
testcase_18 AC 779 ms
40,536 KB
testcase_19 AC 794 ms
41,308 KB
testcase_20 AC 711 ms
41,428 KB
testcase_21 AC 790 ms
40,528 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: methods `get_dist`, `get_len`, and `on_path` are never used
  --> src/main.rs:84:8
   |
13 | impl LCA {
   | -------- methods in this implementation
...
84 |     fn get_dist(&self, left: usize, right: usize) -> usize {
   |        ^^^^^^^^
...
89 |     fn get_len(&self, left: usize, right: usize) -> usize {
   |        ^^^^^^^
...
93 |     fn on_path(&self, target: usize, left: usize, right: usize) -> bool {
   |        ^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use std::{mem::swap, collections::VecDeque};

const INF: usize = 1usize << 60;

struct LCA {
    root: usize,
    paths: Vec<Vec<(usize, usize)>>,
    parents: Vec<Vec<usize>>,
    dists: Vec<usize>,
    lens: Vec<usize>,
}

impl LCA {
    fn new(root: usize, paths: &Vec<Vec<(usize, usize)>>) -> LCA {
        let mut temp = LCA {
            root,
            paths: paths.clone().to_owned(),
            parents: vec![],
            dists: vec![],
            lens: vec![]
        };
        temp._build();
        temp
    }

    fn _build(&mut self) {
        let n = self.paths.len();
        let mut k = 1usize;
        while (1usize << k) < n {
            k += 1;
        }
        self.parents = vec![vec![n; n]; k];
        self.dists = vec![INF; n];
        self.lens = vec![INF; n];
        self._dfs(self.root, self.root, 0, 0);
        for i in 0..k-1 {
            for j in 0..n {
                if self.parents[i][j] == self.root {
                    self.parents[i + 1][j] = self.root;
                } else {
                    self.parents[i + 1][j] = self.parents[i][self.parents[i][j]];
                }
            }
        }
    }

    fn _dfs(&mut self, v: usize, u: usize, dist: usize, len: usize) {
        self.parents[0][v] = u;
        self.dists[v] = dist;
        self.lens[v] = len;
        for i in 0..self.paths[v].len() {
            let (vv, cost) = self.paths[v][i];
            if vv != u {
                self._dfs(vv, v, dist + cost, len + 1);
            }
        }
    }

    fn ancester(&self, left: usize,  right: usize) -> usize {
        let mut l = left;
        let mut r = right;
        if self.lens[l] < self.lens[r] {
            swap(&mut l, &mut r);
        }
        let lim = self.parents.len();
        for i in 0..lim {
            if (((self.lens[l] - self.lens[r]) >> i) & 1) == 1 {
                l = self.parents[i][l];
            }
        }
        if l == r {
            return l;
        }
        for i in (0..lim).rev() {
            if self.parents[i][l] != self.parents[i][r] {
                l = self.parents[i][l];
                r = self.parents[i][r];
            }
        }
        self.parents[0][l]
    }

    // 距離の設定がある場合
    fn get_dist(&self, left: usize, right: usize) -> usize {
        self.dists[left] + self.dists[right] - 2 * self.dists[self.ancester(left, right)]
    }

    // コスト1の場合 = 辺の本数
    fn get_len(&self, left: usize, right: usize) -> usize {
        self.lens[left] + self.lens[right] - 2 * self.lens[self.ancester(left, right)]
    }

    fn on_path(&self, target: usize, left: usize, right: usize) -> bool {
        self.get_len(target, left) + self.get_len(target, right) == self.get_len(left, right)
    }
}


fn main() {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).ok();
    let n: usize = n.trim().parse().unwrap();
    let mut paths = vec![vec![]; n];
    for _ in 0..n-1 {
        let mut temp = String::new();
        std::io::stdin().read_line(&mut temp).ok();
        let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
        let u = temp[0];
        let v = temp[1];
        let w = temp[2];
        paths[u].push((v, w));
        paths[v].push((u, w));
    }
    let mut q = String::new();
    std::io::stdin().read_line(&mut q).ok();
    let q: usize = q.trim().parse().unwrap();
    let queries = (0..q).map(|_| {
            let mut temp = String::new();
            std::io::stdin().read_line(&mut temp).ok();
            let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
            (temp[0], temp[1], temp[2])
        })
        .collect::<Vec<_>>();
    
    let lca = LCA::new(0, &paths);
    let mut dists = vec![INF; n];
    dists[0] = 0;
    let mut deque = VecDeque::new();
    deque.push_back(0);
    while let Some(u) = deque.pop_front() {
        for &(v, w) in paths[u].iter() {
            if dists[v] != INF { continue; }
            dists[v] = dists[u] + w;
            deque.push_back(v);
        }
    }
    for &(x, y, z) in queries.iter() {
        let mut result = INF;
        for &(x, y, z) in vec![(x,y,z), (x,z,y), (y,x,z), (y,z,x), (z,x,y), (z,y,x)].iter() {
            let temproot = lca.ancester(x, y);
            let mut res = dists[x] + dists[y] - 2 * dists[temproot];
            let root = lca.ancester(temproot, z);
            res += dists[temproot] + dists[z] - 2 * dists[root];
            result = result.min(res);
        }
        println!("{}", result);
    }
}
0