結果

問題 No.417 チューリップバブル
ユーザー ngtkanangtkana
提出日時 2024-06-10 20:29:53
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 82 ms / 2,000 ms
コード長 3,044 bytes
コンパイル時間 13,967 ms
コンパイル使用メモリ 388,372 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-10 20:30:24
合計ジャッジ時間 16,265 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 4 ms
6,944 KB
testcase_11 AC 15 ms
6,940 KB
testcase_12 AC 12 ms
6,940 KB
testcase_13 AC 5 ms
6,940 KB
testcase_14 AC 17 ms
6,940 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 12 ms
6,940 KB
testcase_18 AC 13 ms
6,944 KB
testcase_19 AC 11 ms
6,940 KB
testcase_20 AC 38 ms
6,940 KB
testcase_21 AC 37 ms
6,940 KB
testcase_22 AC 36 ms
6,940 KB
testcase_23 AC 41 ms
6,944 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 32 ms
6,940 KB
testcase_26 AC 4 ms
6,944 KB
testcase_27 AC 30 ms
6,940 KB
testcase_28 AC 39 ms
6,940 KB
testcase_29 AC 38 ms
6,944 KB
testcase_30 AC 45 ms
6,944 KB
testcase_31 AC 44 ms
6,940 KB
testcase_32 AC 1 ms
6,940 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 12 ms
6,944 KB
testcase_35 AC 82 ms
6,940 KB
testcase_36 AC 75 ms
6,944 KB
testcase_37 AC 69 ms
6,940 KB
testcase_38 AC 61 ms
6,940 KB
testcase_39 AC 54 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;
use std::collections::HashMap;

fn main() {
    input! {
        n: usize,
        m: usize,
        values: [u64; n],
        edges: [(usize, usize, usize); n - 1],
    }
    let mut g = vec![Vec::new(); n];
    let mut weight = HashMap::new();
    for &(i, j, w) in &edges {
        g[i].push(j);
        g[j].push(i);
        weight.insert((i, j), w);
        weight.insert((j, i), w);
    }
    let mut sorted = Vec::new();
    let mut parent = vec![usize::MAX; n];
    let mut stack = vec![0];
    while let Some(i) = stack.pop() {
        sorted.push(i);
        g[i].retain(|&j| j != parent[i]);
        for &j in &g[i] {
            stack.push(j);
            parent[j] = i;
        }
    }
    let weights = (0..n)
        .map(|i| if i == 0 { 0 } else { weight[&(parent[i], i)] })
        .collect::<Vec<_>>();

    let dp = tree_dp(
        &O {
            max: m / 2,
            weights: &weights,
            values: &values,
        },
        &g,
        &sorted,
    );
    let ans = dp[0].f.iter().copied().max().unwrap().unwrap();
    println!("{ans}");
}

#[derive(Debug, Clone, PartialEq, Default)]
struct Value {
    f: Vec<Option<u64>>,
}

struct O<'a> {
    max: usize,
    weights: &'a [usize],
    values: &'a [u64],
}
impl Op for O<'_> {
    type Acc = Value;
    type Value = Value;

    fn f(&self, value: &Self::Value, index: usize) -> Self::Acc {
        let w = self.weights[index].min(self.max + 1);
        let mut f = value.f.clone();
        f.rotate_right(w);
        f[..w].iter_mut().for_each(|x| *x = None);
        f[0] = Some(0);
        Self::Acc { f }
    }

    fn g(&self, acc: &Self::Acc, index: usize) -> Self::Value {
        let v = self.values[index];
        let mut f = acc.f.clone();
        f.iter_mut().for_each(|x| *x = x.map(|x| x + v));
        Self::Value { f }
    }

    fn identity(&self) -> Self::Acc {
        let mut f = vec![None; self.max + 1];
        f[0] = Some(0);
        Self::Acc { f }
    }

    fn mul(&self, lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc {
        let mut f = vec![None; self.max + 1];
        f[0] = Some(0);
        for (i, &x) in lhs.f.iter().enumerate() {
            for (j, &y) in rhs.f[..=self.max - i].iter().enumerate() {
                f[i + j] = f[i + j].max(x.zip(y).map(|(x, y)| x + y));
            }
        }
        Self::Acc { f }
    }
}

pub trait Op {
    type Value: Default + Clone;
    type Acc: Default + Clone;

    fn f(&self, value: &Self::Value, index: usize) -> Self::Acc;
    fn g(&self, acc: &Self::Acc, index: usize) -> Self::Value;
    fn identity(&self) -> Self::Acc;
    fn mul(&self, lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc;
}

pub fn tree_dp<O: Op>(o: &O, g: &[Vec<usize>], sorted: &[usize]) -> Vec<O::Value> {
    let mut dp = vec![O::Value::default(); g.len()];
    for &i in sorted.iter().rev() {
        dp[i] = o.g(
            &g[i]
                .iter()
                .fold(o.identity(), |acc, &j| o.mul(&acc, &o.f(&dp[j], j))),
            i,
        );
    }
    dp
}
0