結果

問題 No.3113 The farthest point
ユーザー lumc_
提出日時 2025-04-19 19:30:13
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 824 ms / 2,000 ms
コード長 1,299 bytes
コンパイル時間 15,737 ms
コンパイル使用メモリ 388,152 KB
実行使用メモリ 80,988 KB
最終ジャッジ日時 2025-04-19 19:30:43
合計ジャッジ時間 28,105 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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