#1007004 (Rust) No.763 Noelちゃんと木遊び

提出ソース

結果

問題	No.763 Noelちゃんと木遊び
ユーザー	Haar
提出日時	2024-09-03 19:21:15
言語	Rust (1.77.0)
結果	AC
実行時間	85 ms / 2,000 ms
コード長	13,670 bytes
コンパイル時間	13,084 ms
コンパイル使用メモリ	402,604 KB
実行使用メモリ	31,164 KB
最終ジャッジ日時	2024-09-03 19:21:31
合計ジャッジ時間	16,125 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	34 ms 31,164 KB
testcase_01	AC	16 ms 7,168 KB
testcase_02	AC	34 ms 14,004 KB
testcase_03	AC	21 ms 10,124 KB
testcase_04	AC	15 ms 7,808 KB
testcase_05	AC	23 ms 9,768 KB
testcase_06	AC	85 ms 16,624 KB
testcase_07	AC	44 ms 16,012 KB
testcase_08	AC	23 ms 10,496 KB
testcase_09	AC	16 ms 7,552 KB
testcase_10	AC	6 ms 6,944 KB
testcase_11	AC	60 ms 16,732 KB
testcase_12	AC	44 ms 15,192 KB
testcase_13	AC	45 ms 14,992 KB
testcase_14	AC	32 ms 13,604 KB
testcase_15	AC	22 ms 9,856 KB
testcase_16	AC	4 ms 6,940 KB
testcase_17	AC	19 ms 10,044 KB
testcase_18	AC	54 ms 16,520 KB
testcase_19	AC	42 ms 15,332 KB
testcase_20	AC	45 ms 15,412 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused imports: `get`, `input`, `utils::join_str::*`
  --> src/main.rs:7:9
   |
7  |         get, input,
   |         ^^^  ^^^^^
...
10 |         utils::join_str::*,
   |         ^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

ソースコード

raw source code

// Bundled at 2024/09/03 19:20:39 +09:00
// Author: Haar

pub mod main {
    use super::*;
    use haar_lib::{
        get, input,
        tree::{tree_dp::*, *},
        utils::fastio::*,
        utils::join_str::*,
    };
    #[allow(unused_imports)]
    use std::cell::RefCell;
    use std::cmp::max;
    #[allow(unused_imports)]
    use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
    #[allow(unused_imports)]
    use std::io::Write;
    #[allow(unused_imports)]
    use std::rc::Rc;
    #[derive(Clone, Default)]
    pub struct Problem {}
    impl Problem {
        pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
            let mut io = FastIO::new();
            let n = io.read_usize();
            let mut builder = TreeBuilder::new(n);
            for _ in 0..n - 1 {
                let u = io.read_usize() - 1;
                let v = io.read_usize() - 1;
                builder.extend(Some(TreeEdge::new(u, v, (), ())));
            }
            let tree = builder.build();
            let id = (0, 0);
            let up = Box::new(|a: (u64, u64), _| a);
            let merge = Box::new(|a: (u64, u64), b: (u64, u64)| {
                (a.0 + max(b.0 - 1, b.1), a.1 + max(b.0, b.1))
            });
            let apply = Box::new(|a: (u64, u64), _| (a.0 + 1, a.1));
            let dp = TreeDP::new(id, merge, up, apply);
            let dp = dp.run(&tree, 0);
            let ans = max(dp[0].0, dp[0].1);
            io.writeln(ans);
            Ok(())
        }
    }
}
fn main() {
    main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod macros {
    pub mod io {
        #[macro_export]
        macro_rules! get {
    ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
        {
            let n = $num;
            (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
        }
    };
    ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
        ($(get!($in, $type $(as $to)*)),*)
    };
    ( $in:ident, i8 ) => { $in.read_i64() as i8 };
    ( $in:ident, i16 ) => { $in.read_i64() as i16 };
    ( $in:ident, i32 ) => { $in.read_i64() as i32 };
    ( $in:ident, i64 ) => { $in.read_i64() };
    ( $in:ident, isize ) => { $in.read_i64() as isize };
    ( $in:ident, u8 ) => { $in.read_u64() as u8 };
    ( $in:ident, u16 ) => { $in.read_u64() as u16 };
    ( $in:ident, u32 ) => { $in.read_u64() as u32 };
    ( $in:ident, u64 ) => { $in.read_u64() };
    ( $in:ident, usize ) => { $in.read_u64() as usize };
    ( $in:ident, [char] ) => { $in.read_chars() };
    ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
        #[macro_export]
        macro_rules! input {
    ( @inner $in:ident, mut $name:ident : $type:tt ) => {
        let mut $name = get!($in, $type);
    };
    ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
        let mut $name = get!($in, $type as $to);
    };
    ( @inner $in:ident, $name:ident : $type:tt ) => {
        let $name = get!($in, $type);
    };
    ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
        let $name = get!($in, $type as $to);
    };
    ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
        $(input!(@inner $in, $($names)* : $type $(as $to)*);)*
    }
}
    }
}
pub mod tree {
    pub mod tree_dp {
        use crate::tree::*;
        pub struct TreeDP<'a, Weight, T> {
            id: T,
            merge: Box<dyn 'a + Fn(T, T) -> T>,
            up: Box<dyn 'a + Fn(T, (usize, Weight)) -> T>,
            apply: Box<dyn 'a + Fn(T, usize) -> T>,
        }
        impl<'a, Weight, T> TreeDP<'a, Weight, T>
        where
            Weight: Copy,
            T: Clone,
        {
            pub fn new(
                id: T,
                merge: Box<impl 'a + Fn(T, T) -> T>,
                up: Box<impl 'a + Fn(T, (usize, Weight)) -> T>,
                apply: Box<impl 'a + Fn(T, usize) -> T>,
            ) -> Self {
                Self {
                    id,
                    merge,
                    up,
                    apply,
                }
            }

            pub fn run<E: TreeEdgeTrait<Weight = Weight>>(
                &self,
                tree: &Tree<E>,
                root: usize,
            ) -> Vec<T> {
                let size = tree.len();
                let mut ret = vec![self.id.clone(); size];
                self.__dfs(tree, root, None, &mut ret);
                ret
            }

            fn __dfs<E: TreeEdgeTrait<Weight = Weight>>(
                &self,
                tree: &Tree<E>,
                cur: usize,
                par: Option<usize>,
                ret: &mut Vec<T>,
            ) {
                for e in tree.nodes[cur].neighbors() {
                    if Some(e.to()) == par {
                        continue;
                    }
                    self.__dfs(tree, e.to(), Some(cur), ret);
                    let temp = (self.up)(ret[e.to()].clone(), (e.to(), e.weight()));
                    ret[cur] = (self.merge)(ret[cur].clone(), temp);
                }
                ret[cur] = (self.apply)(ret[cur].clone(), cur);
            }
        }
    }
    pub trait TreeEdgeTrait {
        type Weight;
        fn from(&self) -> usize;
        fn to(&self) -> usize;
        fn weight(&self) -> Self::Weight;
        fn rev(self) -> Self;
    }
    #[derive(Clone, Debug)]
    pub struct TreeEdge<T, I> {
        pub from: usize,
        pub to: usize,
        pub weight: T,
        pub index: I,
    }
    impl<T, I> TreeEdge<T, I> {
        pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
            Self {
                from,
                to,
                weight,
                index,
            }
        }
    }
    impl<T: Clone, I> TreeEdgeTrait for TreeEdge<T, I> {
        type Weight = T;

        #[inline]

        fn from(&self) -> usize {
            self.from
        }

        #[inline]

        fn to(&self) -> usize {
            self.to
        }

        #[inline]

        fn weight(&self) -> Self::Weight {
            self.weight.clone()
        }

        fn rev(mut self) -> Self {
            std::mem::swap(&mut self.from, &mut self.to);
            self
        }
    }
    #[derive(Clone, Debug, Default)]
    pub struct TreeNode<E> {
        pub parent: Option<E>,
        pub children: Vec<E>,
    }
    impl<E: TreeEdgeTrait> TreeNode<E> {
        pub fn neighbors(&self) -> impl DoubleEndedIterator<Item = &E> {
            self.children.iter().chain(self.parent.iter())
        }

        pub fn neighbors_size(&self) -> usize {
            self.children.len() + self.parent.as_ref().map_or(0, |_| 1)
        }
    }
    pub struct TreeBuilder<E> {
        nodes: Vec<TreeNode<E>>,
    }
    impl<E: TreeEdgeTrait + Clone> TreeBuilder<E> {
        pub fn new(size: usize) -> Self {
            Self {
                nodes: vec![
                    TreeNode {
                        parent: None,
                        children: vec![],
                    };
                    size
                ],
            }
        }

        pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
            for e in edges {
                self.nodes[e.from()].children.push(e.clone());
                self.nodes[e.to()].children.push(e.rev());
            }
        }

        pub fn build(self) -> Tree<E> {
            Tree {
                nodes: self.nodes,
                root: None,
            }
        }
    }
    pub struct RootedTreeBuilder<E> {
        nodes: Vec<TreeNode<E>>,
        root: usize,
    }
    impl<E: TreeEdgeTrait + Clone> RootedTreeBuilder<E> {
        pub fn new(size: usize, root: usize) -> Self {
            Self {
                nodes: vec![
                    TreeNode {
                        parent: None,
                        children: vec![],
                    };
                    size
                ],
                root,
            }
        }

        pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
            for e in edges {
                assert!(self.nodes[e.to()].parent.is_none());
                self.nodes[e.from()].children.push(e.clone());
                self.nodes[e.to()].parent.replace(e.rev());
            }
        }

        pub fn build(self) -> Tree<E> {
            Tree {
                nodes: self.nodes,
                root: Some(self.root),
            }
        }
    }
    #[derive(Clone, Debug)]
    pub struct Tree<E> {
        nodes: Vec<TreeNode<E>>,
        root: Option<usize>,
    }
    impl<E> Tree<E> {
        pub fn nodes_iter(&self) -> impl Iterator<Item = &TreeNode<E>> {
            self.nodes.iter()
        }

        pub fn len(&self) -> usize {
            self.nodes.len()
        }

        pub fn is_empty(&self) -> bool {
            self.nodes.is_empty()
        }

        pub fn root(&self) -> Option<usize> {
            self.root
        }
    }
}
pub mod utils {
    pub mod fastio {
        use std::fmt::Display;
        use std::io::{Read, Write};
        pub struct FastIO {
            in_bytes: Vec<u8>,
            in_cur: usize,
            out_buf: std::io::BufWriter<std::io::Stdout>,
        }
        impl FastIO {
            pub fn new() -> Self {
                let mut s = vec![];
                std::io::stdin().read_to_end(&mut s).unwrap();
                let cout = std::io::stdout();
                Self {
                    in_bytes: s,
                    in_cur: 0,
                    out_buf: std::io::BufWriter::new(cout),
                }
            }

            #[inline]
            pub fn getc(&mut self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    self.in_cur += 1;
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }

            #[inline]
            pub fn peek(&self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }

            #[inline]
            pub fn skip(&mut self) {
                while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
                    self.in_cur += 1;
                }
            }

            pub fn read_u64(&mut self) -> u64 {
                self.skip();
                let mut ret: u64 = 0;
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
                    self.in_cur += 1;
                }
                ret
            }

            pub fn read_u32(&mut self) -> u32 {
                self.read_u64() as u32
            }

            pub fn read_usize(&mut self) -> usize {
                self.read_u64() as usize
            }

            pub fn read_i64(&mut self) -> i64 {
                self.skip();
                let mut ret: i64 = 0;
                let minus = if self.peek() == Some(b'-') {
                    self.in_cur += 1;
                    true
                } else {
                    false
                };
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
                    self.in_cur += 1;
                }
                if minus {
                    ret = -ret;
                }
                ret
            }

            pub fn read_i32(&mut self) -> i32 {
                self.read_i64() as i32
            }

            pub fn read_isize(&mut self) -> isize {
                self.read_i64() as isize
            }

            pub fn read_f64(&mut self) -> f64 {
                self.read_chars()
                    .into_iter()
                    .collect::<String>()
                    .parse()
                    .unwrap()
            }

            pub fn read_chars(&mut self) -> Vec<char> {
                self.skip();
                let mut ret = vec![];
                while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur] as char);
                    self.in_cur += 1;
                }
                ret
            }

            pub fn write_rev<T: Display>(&mut self, s: T) {
                let mut s = format!("{}", s);
                let s = unsafe { s.as_bytes_mut() };
                s.reverse();
                self.out_buf.write_all(s).unwrap();
            }

            pub fn write<T: Display>(&mut self, s: T) {
                self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
            }

            pub fn writeln_rev<T: Display>(&mut self, s: T) {
                self.write_rev(s);
                self.out_buf.write_all(&[b'\n']).unwrap();
            }

            pub fn writeln<T: Display>(&mut self, s: T) {
                self.write(s);
                self.out_buf.write_all(&[b'\n']).unwrap();
            }
        }
        impl Drop for FastIO {
            fn drop(&mut self) {
                self.out_buf.flush().unwrap();
            }
        }
    }
    pub mod join_str {
        pub trait JoinStr {
            fn join_str(self, _: &str) -> String;
        }
        impl<T, I> JoinStr for I
        where
            T: ToString,
            I: Iterator<Item = T>,
        {
            fn join_str(self, s: &str) -> String {
                self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
            }
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード