#389731 (Rust) No.900 aδδitivee

• 問題: No.900 aδδitivee
• ユーザー: ziita
• 提出日時: 2019-10-13 12:54:29
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 6,618 bytes
• コンパイル時間: 15,492 ms
• コンパイル使用メモリ: 382,256 KB
• 実行使用メモリ: 28,432 KB
• 最終ジャッジ日時: 2024-12-14 19:01:26
• 合計ジャッジ時間: 18,910 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	WA * 2
other	WA * 27

コンパイルメッセージ

warning: variable does not need to be mutable
   --> src/main.rs:127:13
    |
127 |         let mut lazy_data = vec![None; size_p2 * 2];
    |             ----^^^^^^^^^
    |             |
    |             help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: unused variable: `q`
   --> src/main.rs:227:9
    |
227 |         q: usize,
    |         ^
    |
help: `q` is captured in macro and introduced a unused variable
   --> src/main.rs:36:13
    |
36  |           let $var = read_value!($next, $t);
    |               ^^^^
...
224 | /     input! {
225 | |         n: usize,
226 | |         e: [[usize;3];n-1],
227 | |         q: usize,
228 | |     }    
    | |_____- in this macro invocation
    = note: `#[warn(unused_variables)]` on by default
    = note: this warning originates in the macro `input_inner` which comes from the expansion of the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: unused variable: `seg`
   --> src/main.rs:236:13
    |
236 |     let mut seg = SEG::from_vec(euler.W);
    |             ^^^ help: if this is intentional, prefix it with an underscore: `_seg`

warning: variable does not need to be mutable
   --> src/main.rs:236:9
    |
236 |     let mut seg = SEG::from_vec(euler.W);
    |         ----^^^
    |         |
    |         help: remove this `mut`

ソースコード

#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(non_camel_case_types)]
#![allow(non_snake_case)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;
use std::io::{Write, BufWriter};

// static MOD: usize = 998244353;
static MOD: usize = 1000000007;

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp;
use std::marker::PhantomData;

pub trait Monoid<T> {
    fn id() -> Option<T> {
        None
    }
    fn op(l: &Option<T>, r: &Option<T>) -> Option<T>;
    fn lazy_op(l: &Option<T>, r: &Option<T>) -> Option<T>;
}

pub struct MinOp<T: Ord> {
    phantom: PhantomData<T>,
}

impl<T: Ord + Clone + Add<Output=T>> Monoid<T> for MinOp<T> {
    #[inline]
    // add
    fn op(l: &Option<T>, r: &Option<T>) -> Option<T> {
        match (l.clone(), r.clone()) {
            (Some(l), Some(r)) => Some(l+r),
            (Some(l), None) => Some(l),
            (None, Some(r)) => Some(r),
            (None, None) => None,
        }
    }
    // add
    fn lazy_op(l: &Option<T>, r: &Option<T>) -> Option<T> {
        match (l.clone(), r.clone()) {
            (Some(l), Some(r)) => Some(l+r),
            (Some(l), None) => Some(l),
            (None, Some(r)) => Some(r),
            (None, None) => None,
        }
    }
}

pub struct SegmentTree<M: Monoid<T>, T: Clone> {
    phantom: PhantomData<M>,
    data: Vec<Option<T>>,
    lazy_data: Vec<Option<T>>,
    size: usize,
    size_p2: usize,
}

impl<M: Monoid<T>, T: Clone> SegmentTree<M, T> {
    pub fn from_vec(v: Vec<T>) -> SegmentTree<M, T> {
        let size = v.len();
        let mut size_p2 = 1;
        while size_p2 < v.len() {
            size_p2 *= 2;
        }
        let mut data = vec![None; size_p2 * 2];
        for (i, x) in v.into_iter().enumerate() {
            data[size_p2 + i] = Some(x);
        }
        for i in (0..size_p2).rev() {
            data[i] = M::op(&data[i * 2 + 0], &data[i * 2 + 1]);
        }
        let mut lazy_data = vec![None; size_p2 * 2];
        SegmentTree {
            phantom: PhantomData,
            data: data,
            lazy_data: lazy_data,
            size: size,
            size_p2: size_p2,
        }
    }

    pub fn size(&self) -> usize {
        self.size
    }

    pub fn eval(&mut self, l: usize, r: usize, k: usize){
        if self.lazy_data[k].is_some() {
            self.data[k] = M::lazy_op(&self.data[k], &self.lazy_data[k]);
            if r-l>1 {
                self.data[2*k+0] = M::lazy_op(&self.data[2*k+0], &self.lazy_data[k]);
                self.data[2*k+1] = M::lazy_op(&self.data[2*k+1], &self.lazy_data[k]);
            }
            self.lazy_data[k] = None;
        }
    }

    pub fn lazy_update(&mut self, a: usize, b: usize, l: usize, r: usize, k: usize, value: T) {
        // assert!(l <= r && r <= self.size);
        self.eval(l,r,k);
        if b<=l || r<=a {return;}
        if a<=l && r<=b {
            self.lazy_data[k] = Some(value);
            self.eval(l,r,k);
        }
        else{
            self.lazy_update(a,b,l,(l+r)/2,2*k+0,value.clone());
            self.lazy_update(a,b,(l+r)/2,r,2*k+1,value.clone());
            self.data[k] = M::op(&self.data[2*k+0], &self.data[2*k+1]);
        }
    }

    pub fn update(&mut self, a: usize, b:usize, value: T){
        self.lazy_update(a,b,0,self.size_p2,1,value);
    }

    pub fn lazy_query(&mut self, a: usize, b: usize, l: usize, r: usize, k: usize) -> Option<T> {
        self.eval(l,r,k);
        if a<=l && r<=b {return self.data[k].clone();}
        if b<=l || r<=a {return None;}
        let res1 = self.lazy_query(a, b, l, (l+r)/2, 2*k+0);
        let res2 = self.lazy_query(a, b, (l+r)/2, r, 2*k+1);
        M::op(&res1, &res2)
    }

    pub fn query(&mut self, l: usize, r: usize) -> Option<T> {
        self.lazy_query(l,r,0,self.size_p2,1)
    }
}

struct euler{
    L: Vec<usize>,
    R: Vec<usize>,
    D: Vec<usize>,
    W: Vec<i64>,
    edge: Vec<Vec<[usize;2]>>,
    n: usize,
    idx: usize,
}

impl euler{
    fn new(n: usize) -> euler{
        euler{
            L: vec![0;2*n],
            R: vec![0;2*n],
            D: vec![0;2*n],
            W: vec![0;2*n],
            edge: vec![vec![]; n],
            n: n,
            idx: 0,
        }
    }
    fn add_edge(&mut self, s: usize, t: usize, w: usize) {
        self.edge[s].push([t,w]);
    }
    fn dfs(&mut self, cur: usize, p: usize, d: usize, dist: i64){
        self.L[cur] = self.idx;
        self.W[self.L[cur]] = dist;
        for i in self.edge[cur].clone() {
            if i[0]==p {continue;}
            self.idx += 1;
            self.dfs(i[0], cur, d+1, dist+i[1] as i64);
        }
        self.idx += 1;
        self.R[cur] = self.idx;
    }
}

fn solve() {
    input! {
        n: usize,
        e: [[usize;3];n-1],
        q: usize,
    }    
    let mut euler = euler::new(n);
    for i in e {
        euler.add_edge(i[0], i[1], i[2]);
    }
    euler.dfs(0,n+1,0,0);

    pub type SEG<T> = SegmentTree<MinOp<T>, T>;
    let mut seg = SEG::from_vec(euler.W);

}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}