結果

問題 No.3113 The farthest point
ユーザー rhoo
提出日時 2025-04-18 21:10:36
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 149 ms / 2,000 ms
コード長 1,651 bytes
コンパイル時間 13,624 ms
コンパイル使用メモリ 400,776 KB
実行使用メモリ 32,528 KB
最終ジャッジ日時 2025-04-18 21:11:42
合計ジャッジ時間 14,703 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,collections::*,iter::*};
use proconio::{marker::*,*};


#[fastout]
fn main(){
    input!{
        n:usize,
        es:[(Usize1,Usize1,i64);n-1],
    }

    let mut g=vec![vec![];n];
    for &(u,v,w) in &es{
        g[u].push((v,w));
        g[v].push((u,w));
    }

    let max={
        let mut dp=vec![0;n];
        fn rec(g:&Vec<Vec<(usize,i64)>>,p:usize,v:usize,dp:&mut [i64]){
            for &(nv,cost) in &g[v]{
                if p==nv{
                    continue;
                }
                rec(g,v,nv,dp);
                dp[v]=dp[v].max(dp[nv]+cost);
            }
        }
        rec(&g,!0,0,&mut dp);
        dp
    };

    // eprintln!("{:?}",max);

    let mut ans=0;
    fn rec(g:&Vec<Vec<(usize,i64)>>,p:usize,v:usize,cur:i64,max:&[i64],ans:&mut i64){
        assert!(0<=cur);
        
        let mut max1=cur;
        let mut max2=0;
        for &(nv,cost) in &g[v]{
            if p==nv{
                continue;
            }
            let new=(max[nv]+cost).max(0);
            if max1<=new{
                (max1,max2)=(new,max1);
            } else if max2<new{
                max2=new;
            }
        }

        *ans=(max1+max2).max(*ans);

        for &(nv,cost) in &g[v]{
            if p==nv{
                continue;
            }

            let new=(max[nv]+cost).max(0);

            let next=if new==max1{
                max2
            } else{
                max1
            };

            rec(g,v,nv,(next+cost).max(0),max,ans);
        }
    }

    rec(&g,!0,0,0,&max,&mut ans);

    println!("{ans}");
}
0