#629075 (Rust) No.1424 Ultrapalindrome

• 問題: No.1424 Ultrapalindrome
• ユーザー: ikd
• 提出日時: 2021-03-13 00:38:45
• 言語: Rust (1.77.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	0 ms; 5,248 KB
testcase_04	AC	0 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	0 ms; 5,248 KB
testcase_09	AC	40 ms; 9,728 KB
testcase_10	AC	38 ms; 9,728 KB
testcase_11	AC	26 ms; 7,168 KB
testcase_12	AC	39 ms; 9,344 KB
testcase_13	AC	10 ms; 5,248 KB
testcase_14	AC	28 ms; 7,680 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	22 ms; 6,784 KB
testcase_17	AC	27 ms; 7,424 KB
testcase_18	AC	18 ms; 6,004 KB
testcase_19	AC	29 ms; 7,424 KB
testcase_20	AC	8 ms; 5,248 KB
testcase_21	AC	24 ms; 6,528 KB
testcase_22	AC	15 ms; 5,248 KB
testcase_23	AC	4 ms; 5,248 KB
testcase_24	AC	7 ms; 5,248 KB
testcase_25	AC	6 ms; 5,248 KB
testcase_26	AC	38 ms; 8,448 KB
testcase_27	AC	51 ms; 13,256 KB
testcase_28	AC	41 ms; 20,608 KB
testcase_29	AC	41 ms; 20,608 KB
testcase_30	AC	38 ms; 15,232 KB
testcase_31	AC	39 ms; 15,360 KB

コンパイルメッセージ

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)

ソースコード

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()
    }
}