つらい / typical90 003

天気が悪いせいかなんとなくつらい。

---

競プロ典型 90 問

• 003 - Longest Circular Road（★4） https://atcoder.jp/contests/typical90/tasks/typical90_c
  • 提出: https://atcoder.jp/contests/typical90/submissions/50497988
  • N 頂点で N - 1 辺で連結なので木
  • 任意の 2 つの頂点を結ぶ経路は 1 通りしかない
  • 最長の経路の頂点を結べば最大のスコアになる
  • 適当な根付き木で最も遠い頂点を探し、そこから最も遠い頂点を探せば最長の経路になるのでそこに 1 足す

use std::collections::VecDeque;

use proconio::{input, marker::Usize1};

fn f(edges: &[Vec<usize>], start: usize) -> Vec<usize> {
    let inf = 1_usize << 60;
    let mut dist = vec![inf; edges.len()];
    let mut deque = VecDeque::new();
    dist[start] = 0_usize;
    deque.push_back(start);
    while let Some(u) = deque.pop_front() {
        for v in edges[u].iter().copied() {
            if dist[v] != inf {
                continue;
            }
            dist[v] = dist[u] + 1;
            deque.push_back(v);
        }
    }
    dist
}

fn main() {
    input! {
        n: usize,
        ab: [(Usize1, Usize1); n - 1],
    };
    let mut edges = vec![vec![]; n];
    for (a, b) in ab {
        edges[a].push(b);
        edges[b].push(a);
    }

    let dist = f(&edges, 0);

    let mut max = (0, 0);
    for (i, d) in dist.iter().copied().enumerate() {
        if d > max.1 {
            max = (i, d);
        }
    }

    let dist = f(&edges, max.0);
    let max = dist.iter().max().unwrap();

    let ans = max + 1;
    println!("{}", ans);
}

---

今日のコミット。

• rust-sandbox 1 commit
  • roguelike-tdd: Add Stairs
• rust-atcoder 1 commit
  • typical90 003