結果

問題 No.2676 A Tourist
ユーザー ngtkanangtkana
提出日時 2024-03-04 05:03:02
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 9,110 bytes
コンパイル時間 12,141 ms
コンパイル使用メモリ 383,160 KB
実行使用メモリ 36,864 KB
最終ジャッジ日時 2024-09-29 23:16:01
合計ジャッジ時間 25,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
6,820 KB
testcase_01 AC 607 ms
13,712 KB
testcase_02 AC 2,272 ms
36,816 KB
testcase_03 AC 255 ms
36,864 KB
testcase_04 AC 703 ms
36,840 KB
testcase_05 AC 935 ms
36,804 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use input::input_array;
use input::input_vec;
use std::collections::HashSet;

fn main() {
    let [n, q] = input_array::<usize, 2>();
    let mut a = input_vec::<i64>();
    let mut g = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let [u, v] = input_array::<usize, 2>();
        let u = u - 1;
        let v = v - 1;
        g[u].push(v);
        g[v].push(u);
    }
    let hld = hld::Hld::new(0, &g);
    for _ in 0..q {
        let [com, arg1, arg2] = input_array::<i64, 3>();
        match com {
            0 => {
                let i = arg1 as usize - 1;
                let x = arg2 as i64;
                a[i] += x;
            }
            1 => {
                let i = arg1 as usize - 1;
                let j = arg2 as usize - 1;
                let path = hld
                    .iter_v(i, j)
                    .flat_map(|(l, r)| (l..=r))
                    .map(|i| hld.ord()[i])
                    .collect::<Vec<_>>();
                let mut vertices = HashSet::new();
                for &x in &path {
                    vertices.insert(x);
                    for &y in &g[x] {
                        vertices.insert(y);
                    }
                }
                let ans = vertices.iter().map(|&x| a[x]).sum::<i64>();
                println!("{}", ans);
            }
            _ => unreachable!(),
        }
    }
}
// input {{{
#[allow(dead_code)]
mod input {
    use std::cell::Cell;
    use std::convert::TryFrom;
    use std::io::stdin;
    use std::io::BufRead;
    use std::io::BufReader;
    use std::io::Lines;
    use std::io::Stdin;
    use std::str::FromStr;
    use std::sync::Mutex;
    use std::sync::Once;
    type Server = Mutex<Lines<BufReader<Stdin>>>;
    static ONCE: Once = Once::new();
    pub struct Lazy(Cell<Option<Server>>);
    unsafe impl Sync for Lazy {}
    fn line() -> String {
        static SYNCER: Lazy = Lazy(Cell::new(None));
        ONCE.call_once(|| {
            SYNCER
                .0
                .set(Some(Mutex::new(BufReader::new(stdin()).lines())));
        });
        unsafe {
            (*SYNCER.0.as_ptr())
                .as_ref()
                .unwrap()
                .lock()
                .unwrap()
                .next()
                .unwrap()
                .unwrap()
        }
    }
    pub trait ForceFromStr: FromStr {
        fn force_from_str(s: &str) -> Self;
    }
    impl<T, E> ForceFromStr for T
    where
        T: FromStr<Err = E>,
        E: std::fmt::Debug,
    {
        fn force_from_str(s: &str) -> Self {
            s.parse().unwrap()
        }
    }
    pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
    where
        T: std::fmt::Debug,
    {
        <[_; N]>::try_from(input_vec()).unwrap()
    }
    pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
        line()
            .split_whitespace()
            .map(T::force_from_str)
            .collect::<Vec<_>>()
    }
    pub fn input<T: ForceFromStr>() -> T {
        T::force_from_str(&line())
    }
}
// }}}
// hld {{{
#[allow(dead_code)]
mod hld {
    use std::mem::swap;
    use std::usize::MAX;
    #[derive(Clone, Debug, Default, Hash, PartialEq, Eq)]
    pub struct Hld {
        child: Vec<Vec<usize>>,
        size: Vec<usize>,
        time: Vec<usize>,
        ord: Vec<usize>,
        parent: Vec<usize>,
        head: Vec<usize>,
    }
    impl Hld {
        pub fn new(root: usize, g: &[Vec<usize>]) -> Self {
            let (child, [size, time, ord, parent, head]) = hld(root, g);
            Self {
                child,
                size,
                time,
                ord,
                parent,
                head,
            }
        }

        pub fn child(&self) -> &[Vec<usize>] {
            &self.child
        }

        pub fn size(&self) -> &[usize] {
            &self.size
        }

        pub fn time(&self) -> &[usize] {
            &self.time
        }

        pub fn ord(&self) -> &[usize] {
            &self.ord
        }

        pub fn parent(&self) -> &[usize] {
            &self.parent
        }

        pub fn head(&self) -> &[usize] {
            &self.head
        }

        pub fn is_adjacent(&self, u: usize, v: usize) -> bool {
            self.parent[u] == v || u == self.parent[v]
        }

        pub fn adjacent_toward(&self, x: usize, toward: usize) -> usize {
            if self.is_ancestor_of(x, toward) {
                self.child[x]
                    .iter()
                    .copied()
                    .find(|&y| self.is_ancestor_of(y, toward))
                    .unwrap()
            } else {
                self.parent[x]
            }
        }

        pub fn dist(&self, u: usize, v: usize) -> usize {
            self.iter_e(u, v).map(|(l, r)| r - l + 1).sum::<usize>()
        }

        pub fn lca(&self, u: usize, v: usize) -> usize {
            let (u, v) = self.iter_v(u, v).last().unwrap();
            self.ord[u.min(v)]
        }

        pub fn is_ancestor_of(&self, p: usize, u: usize) -> bool {
            self.lca(p, u) == p
        }

        pub fn between(&self, a: usize, b: usize, c: usize) -> bool {
            let mid = self.time[b];
            self.iter_v(a, c)
                .any(|(left, right)| (left..=right).contains(&mid))
        }

        pub fn iter_v(&self, u: usize, v: usize) -> IterV<'_> {
            IterV {
                hld: self,
                u,
                v,
                finish: false,
            }
        }

        pub fn iter_e(&self, u: usize, v: usize) -> IterE<'_> {
            IterE {
                hld: self,
                u,
                v,
                finish: false,
            }
        }
    }
    #[derive(Clone, Debug, Hash, PartialEq, Eq)]
    pub struct IterV<'a> {
        hld: &'a Hld,
        u: usize,
        v: usize,
        finish: bool,
    }
    impl Iterator for IterV<'_> {
        type Item = (usize, usize);

        fn next(&mut self) -> Option<Self::Item> {
            if self.finish {
                return None;
            }
            let Self { hld, u, v, .. } = self;
            if hld.time[*u] > hld.time[*v] {
                swap(u, v);
            }
            Some(if hld.head[*u] == hld.head[*v] {
                self.finish = true;
                (hld.time[*u], hld.time[*v])
            } else {
                let h = hld.head[*v];
                let ans = (hld.time[h], hld.time[*v]);
                *v = hld.parent[h];
                ans
            })
        }
    }
    #[derive(Clone, Debug, Hash, PartialEq, Eq)]
    pub struct IterE<'a> {
        hld: &'a Hld,
        u: usize,
        v: usize,
        finish: bool,
    }
    impl Iterator for IterE<'_> {
        type Item = (usize, usize);

        fn next(&mut self) -> Option<Self::Item> {
            if self.finish {
                return None;
            }
            let Self { hld, u, v, .. } = self;
            if hld.time[*u] > hld.time[*v] {
                swap(u, v);
            }
            if hld.head[*u] == hld.head[*v] {
                self.finish = true;
                if *u == *v {
                    None
                } else {
                    Some((hld.time[*u] + 1, hld.time[*v]))
                }
            } else {
                let h = hld.head[*v];
                let ans = (hld.time[h], hld.time[*v]);
                *v = hld.parent[h];
                Some(ans)
            }
        }
    }
    fn hld(root: usize, g: &[Vec<usize>]) -> (Vec<Vec<usize>>, [Vec<usize>; 5]) {
        let n = g.len();
        let mut size = vec![1; n];
        let mut child = vec![Vec::<usize>::new(); n];
        dfs(root, root, g, &mut size, &mut child);
        let mut ord = Vec::new();
        let mut time = vec![MAX; n];
        let mut parent = vec![MAX; n];
        let mut head = vec![MAX; n];
        parent[root] = root;
        head[root] = root;
        efs(root, &child, &mut time, &mut ord, &mut parent, &mut head);
        (child, [size, time, ord, parent, head])
    }
    fn dfs(x: usize, p: usize, g: &[Vec<usize>], size: &mut [usize], child: &mut [Vec<usize>]) {
        let mut gx = g[x].iter().copied().filter(|&y| y != p).collect::<Vec<_>>();
        if !gx.is_empty() {
            for &y in &gx {
                dfs(y, x, g, size, child);
                size[x] += size[y];
            }
            let max_position = (0..gx.len()).max_by_key(|&i| size[gx[i]]).unwrap();
            gx.swap(0, max_position);
        }
        child[x] = gx;
    }
    fn efs(
        x: usize,
        g: &[Vec<usize>],
        time: &mut [usize],
        ord: &mut Vec<usize>,
        parent: &mut [usize],
        head: &mut [usize],
    ) {
        time[x] = ord.len();
        ord.push(x);
        if !g[x].is_empty() {
            let h = g[x][0];
            head[h] = head[x];
            parent[h] = x;
            efs(h, g, time, ord, parent, head);
            for &y in &g[x][1..] {
                head[y] = y;
                parent[y] = x;
                efs(y, g, time, ord, parent, head);
            }
        }
    }
}
// }}}
0