結果

問題 No.1424 Ultrapalindrome
コンテスト
ユーザー ikd
提出日時 2021-03-13 00:38:45
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 4,623 bytes
コンパイル時間 11,445 ms
コンパイル使用メモリ 379,260 KB
実行使用メモリ 20,608 KB
最終ジャッジ日時 2024-10-14 16:30:19
合計ジャッジ時間 13,275 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: trailing semicolon in macro used in expression position
  --> src/main.rs:25:39
   |
25 |               $a = std::cmp::max($a, $b);
   |                                         ^
...
59 | /             chmax!(
60 | |                 tail[i],
61 | |                 tail[i + 1].max(if v == p { par_d } else { sub_d[v] + 1 })
62 | |             )
   | |_____________- in this macro invocation
   |
   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
   = note: for more information, see issue #79813 <https://github.com/rust-lang/rust/issues/79813>
   = note: macro invocations at the end of a block are treated as expressions
   = note: to ignore the value produced by the macro, add a semicolon after the invocation of `chmax`
   = note: `#[warn(semicolon_in_expressions_from_macros)]` on by default
   = note: this warning originates in the macro `chmax` (in Nightly builds, run with -Z macro-backtrace for more info)

ソースコード

diff # 

fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    let n: usize = rd.get();
    let mut g = vec![vec![]; n];
    for _ in 0..(n - 1) {
        let a: usize = rd.get();
        let b: usize = rd.get();
        g[a - 1].push(b - 1);
        g[b - 1].push(a - 1);
    }
    let max = max_dist(&g);
    let min = min_dist(&g);
    if max == min {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn max_dist(g: &Vec<Vec<usize>>) -> usize {
    macro_rules! chmax {
        ($a: expr, $b: expr) => {
            $a = std::cmp::max($a, $b);
        };
    }
    fn dfs(i: usize, p: usize, g: &Vec<Vec<usize>>, par: &mut Vec<usize>, d: &mut Vec<usize>) {
        par[i] = p;
        d[i] = 0;
        for &j in &g[i] {
            if j == p {
                continue;
            }
            dfs(j, i, g, par, d);
            chmax!(d[i], d[j] + 1);
        }
    }
    let n = g.len();
    let mut par = vec![0; n];
    let mut sub_d = vec![0; n];
    dfs(0, std::usize::MAX, &g, &mut par, &mut sub_d);
    let mut d = vec![0; n];
    use std::collections::VecDeque;
    let mut q = VecDeque::new();
    q.push_back((0, std::usize::MAX, 0));
    while let Some((u, p, par_d)) = q.pop_front() {
        d[u] = par_d.max(sub_d[u]);
        let k = g[u].len();
        let mut head = vec![0; k + 1];
        for (i, &v) in g[u].iter().enumerate() {
            chmax!(
                head[i + 1],
                head[i].max(if v == p { par_d } else { sub_d[v] + 1 })
            );
        }
        let mut tail = vec![0; k + 1];
        for (i, &v) in g[u].iter().enumerate().rev() {
            chmax!(
                tail[i],
                tail[i + 1].max(if v == p { par_d } else { sub_d[v] + 1 })
            )
        }
        for (i, &v) in g[u].iter().enumerate() {
            if v != p {
                q.push_back((v, u, 1 + head[i].max(tail[i + 1])));
            }
        }
    }
    d.iter().copied().max().unwrap()
}

fn min_dist(g: &Vec<Vec<usize>>) -> usize {
    let n = g.len();
    use std::collections::VecDeque;
    let mut q = VecDeque::new();
    let mut d = vec![std::usize::MAX; n];
    for i in 0..n {
        if g[i].len() == 1 {
            d[i] = 0;
            q.push_back((i, std::usize::MAX));
        }
    }
    while let Some((u, prev)) = q.pop_front() {
        for &v in &g[u] {
            if v != prev {
                if d[v] != std::usize::MAX {
                    return d[v] + d[u] + 1;
                } else {
                    d[v] = d[u] + 1;
                    q.push_back((v, u));
                }
            }
        }
    }
    unreachable!()
}

pub struct ProconReader<R> {
    r: R,
    l: String,
    i: usize,
}

impl<R: std::io::BufRead> ProconReader<R> {
    pub fn new(reader: R) -> Self {
        Self {
            r: reader,
            l: String::new(),
            i: 0,
        }
    }
    pub fn get<T>(&mut self) -> T
    where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug,
    {
        self.skip_blanks();
        assert!(self.i < self.l.len()); // remain some character
        assert_ne!(&self.l[self.i..=self.i], " ");
        let rest = &self.l[self.i..];
        let len = rest.find(' ').unwrap_or_else(|| rest.len());
        // parse self.l[self.i..(self.i + len)]
        let val = rest[..len]
            .parse()
            .unwrap_or_else(|e| panic!("{:?}, attempt to read `{}`", e, rest));
        self.i += len;
        val
    }
    fn skip_blanks(&mut self) {
        loop {
            match self.l[self.i..].find(|ch| ch != ' ') {
                Some(j) => {
                    self.i += j;
                    break;
                }
                None => {
                    let mut buf = String::new();
                    let num_bytes = self
                        .r
                        .read_line(&mut buf)
                        .unwrap_or_else(|_| panic!("invalid UTF-8"));
                    assert!(num_bytes > 0, "reached EOF :(");
                    self.l = buf
                        .trim_end_matches('\n')
                        .trim_end_matches('\r')
                        .to_string();
                    self.i = 0;
                }
            }
        }
    }
    pub fn get_vec<T>(&mut self, n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug,
    {
        (0..n).map(|_| self.get()).collect()
    }
    pub fn get_chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }
}
0