結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2020-03-30 10:01:00 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 5,484 bytes |
コンパイル時間 | 17,367 ms |
コンパイル使用メモリ | 378,044 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-06-11 15:05:13 |
合計ジャッジ時間 | 19,719 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#![allow(unused)]use kyoproio::*;use std::{io::{self, prelude::*},collections::*,iter,mem::{replace, swap},};fn main() -> io::Result<()> {std::thread::Builder::new().stack_size(50 * 1024 * 1024).spawn(solve)?.join().unwrap();Ok(())}fn solve() {let stdin = io::stdin();let mut kin = KInput::new(stdin.lock());let stdout = io::stdout();let mut out = io::BufWriter::new(stdout.lock());macro_rules! output {($($args:expr),+) => { write!(&mut out, $($args),+) };}macro_rules! outputln {($($args:expr),+) => { output!($($args),+); outputln!() };() => { output!("\n"); if cfg!(debug_assertions) { out.flush(); } }}let n: usize = kin.input();let mut g: Vec<_> = iter::repeat_with(Vec::new).take(n + 1).collect();for _ in 0..n - 1 {let (u, v): (usize, usize) = kin.input();g[u].push(v);g[v].push(u);}let mut dp = vec![[!0, !0]; n + 1];let ans = dfs(&g, 0, 1, 0, &mut dp).max(dfs(&g, 1, 1, 0, &mut dp));outputln!("{}", ans);}pub fn dfs(g: &[Vec<usize>], col: usize, u: usize, p: usize, dp: &mut [[usize; 2]]) -> usize {if dp[u][col] < !0 {return dp[u][col];}dp[u][col] = col;for &v in g[u].iter().filter(|&&v| v != p) {dp[u][col] += if col == 0 {dfs(g, 0, v, u, dp).max(dfs(g, 1, v, u, dp))} else {dfs(g, 0, v, u, dp)};}dp[u][col]}// -----------------------------------------------------------------------------pub mod kyoproio {#![warn(unused)]use std::io::prelude::*;pub trait Input: Sized {fn str(&mut self) -> &str;fn bytes(&mut self) -> &[u8] {self.str().as_ref()}fn input<T: InputParse>(&mut self) -> T {self.input_fallible().expect("input error")}fn input_fallible<T: InputParse>(&mut self) -> Result<T> {T::input(self)}fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {Iter {input: self,_t: std::marker::PhantomData,}}fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {self.iter().take(n).collect()}}pub struct KInput<R> {src: R,buf: String,pos: usize,}impl<R: BufRead> KInput<R> {pub fn new(src: R) -> Self {Self {src,buf: String::with_capacity(1024),pos: 0,}}}impl<R: BufRead> Input for KInput<R> {fn str(&mut self) -> &str {loop {if self.pos >= self.buf.len() {self.pos = 0;self.buf.clear();if self.src.read_line(&mut self.buf).expect("io error") == 0 {return &self.buf;}}let range = self.pos..self.buf[self.pos..].find(|c: char| c.is_ascii_whitespace()).map(|i| i + self.pos).unwrap_or_else(|| self.buf.len());self.pos = range.end + 1;if range.end > range.start {return &self.buf[range];}}}}pub struct Iter<'a, T, I> {input: &'a mut I,_t: std::marker::PhantomData<T>,}impl<'a, T: InputParse, I: Input> Iterator for Iter<'a, T, I> {type Item = T;fn next(&mut self) -> Option<Self::Item> {Some(self.input.input())}}type Result<T> = std::result::Result<T, Box<dyn std::error::Error + 'static>>;pub trait InputParse: Sized {fn input<I: Input>(input: &mut I) -> Result<Self>;}macro_rules! input_from_str_impls {{ $($T:ty)* } => {$(impl InputParse for $T {fn input<I: Input>(input: &mut I) -> Result<Self> {input.str().parse::<$T>().map_err(|e| e.into())}})*};}input_from_str_impls! {String char bool f32 f64isize i8 i16 i32 i64 i128usize u8 u16 u32 u64 u128}macro_rules! input_tuple_impls {($H:ident, $($T:ident),+) => {impl<$H: InputParse, $($T: InputParse),+> InputParse for ($H, $($T),+) {fn input<I: Input>(input: &mut I) -> Result<Self> {Ok(($H::input(input)?, $($T::input(input)?),+))}}input_tuple_impls!($($T),+);};($H:ident) => {};}input_tuple_impls!(A, B, C, D, E, F, G);/*impl<T: InputParse, const N: usize> InputParse for [T; N] {fn input<I: Input>(input: &mut I) -> Result<Self> {let mut a = std::mem::MaybeUninit::<[T; N]>::uninit();for i in 0..N {match T::input(input) {Ok(v) => unsafe { std::ptr::write(&mut (*a.as_mut_ptr())[i], v) },Err(e) => unsafe {std::ptr::drop_in_place(&mut (*a.as_mut_ptr())[..i]);return Err(e);},}}Ok(unsafe { a.assume_init() })}}*/}