結果

問題 No.3113 The farthest point
コンテスト
ユーザー lumc_
提出日時 2025-04-19 19:30:13
言語 Rust
(1.99.0 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 1,299 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
最終ジャッジ日時 2026-10-18 04:20:57
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）

ソースコード

diff #
raw source code 

#![allow(
    dead_code,
    non_snake_case,
    unused_imports,
    unused_mut,
    unused_variables,
    while_true,
    unused_assignments,
    clippy::needless_range_loop,
    clippy::ptr_arg,
    clippy::type_complexity,
    clippy::unnecessary_cast
)]
use proconio::{
    input,
    marker::{Chars, Usize1 as usize1},
};
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};

type Memo = HashMap<usize, HashMap<Option<usize>, i64>>;

fn dfs(v: usize, p: Option<usize>, g: &Vec<Vec<(usize, i64)>>, memo: &mut Memo) -> i64 {
    if let Some(m) = memo.get(&v) {
        if let Some(m) = m.get(&p) {
            return *m;
        }
    }

    let mut max = 0;
    for &(u, w) in g[v].iter() {
        if Some(u) == p {
            continue;
        }
        let d = dfs(u, Some(v), g, memo);
        max = max.max(d + w);
    }
    memo.entry(v).or_default().insert(p, max);
    max
}

fn main() {
    input! {
        N: usize,
        uvw: [(usize1, usize1, i64); N-1],
    };

    let mut g = vec![vec![]; N];
    for &(u, v, w) in uvw.iter() {
        g[u].push((v, w));
        g[v].push((u, w));
    }
    let mut memo = Memo::new();
    let mut max = 0;
    for i in 0..N {
        let d = dfs(i, None, &g, &mut memo);
        max = max.max(d);
    }
    println!("{}", max);
}
0