結果
| 問題 | No.900 aδδitivee |
| ユーザー |
 ziita
|
| 提出日時 | 2019-10-13 12:54:29 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,618 bytes |
| コンパイル時間 | 2,778 ms |
| コンパイル使用メモリ | 168,480 KB |
| 実行使用メモリ | 28,136 KB |
| 最終ジャッジ日時 | 2023-08-21 08:57:17 |
| 合計ジャッジ時間 | 8,494 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
コンパイルメッセージ
warning: unused variable: `q`
--> Main.rs:227:9
|
227 | q: usize,
| ^ help: if this is intentional, prefix it with an underscore: `_q`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `seg`
--> 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
--> 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: variable does not need to be mutable
--> Main.rs:236:9
|
236 | let mut seg = SEG::from_vec(euler.W);
| ----^^^
| |
| help: remove this `mut`
warning: 4 warnings emitted
ソースコード
#![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();
}