結果

問題 No.3134 二分探索木
ユーザー ttkkggww
提出日時 2025-06-08 17:08:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 419 ms / 2,000 ms
コード長 5,029 bytes
コンパイル時間 14,610 ms
コンパイル使用メモリ 377,648 KB
実行使用メモリ 93,140 KB
最終ジャッジ日時 2025-06-08 17:08:30
合計ジャッジ時間 19,794 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `core::mem::swap`
 --> src/main.rs:5:5
  |
5 | use core::mem::swap;
  |     ^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

ソースコード

diff # 

use std::collections::btree_set;
use std::str::{FromStr, SplitWhitespace};
use std::ops::Bound::{Included,Unbounded};
use std::fmt::Debug;
use core::mem::swap;

trait ReadExt {
    fn read<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug;
    fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
        T: Debug;
}
impl<'a> ReadExt for SplitWhitespace<'a> {
    fn read<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        if let Some(word) = self.next() {
            match word.parse::<T>() {
                Ok(res) => {
                    res
                }
                Err(e) => {
                    panic!("Failed to parse '{}' as requested type: {:?}", word, e);
                }
            }
        } else {
            panic!("Failed to read: No more words available for parsing.");
        }
    }
    fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
        T: Debug,
    {
        let mut vec = Vec::with_capacity(n);
        for _ in 0..n {
            let element = self.read::<T>();
            vec.push(element);
        }
        vec
    }
}

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin()).unwrap();
    let mut stdin = stdin.split_whitespace();
    let n = stdin.read::<usize>();
    let v = stdin.read_vec::<usize>(n);
    let mut st = btree_set::BTreeSet::<usize>::new();
    let mut depth = vec![0 as usize;n+1];
    fn get_below_max(x: usize, st: &btree_set::BTreeSet<usize>) -> Option<usize> {
        st.range((Unbounded, Included(&x))).next_back().cloned()
    }
    fn get_above_min(x: usize, st: &btree_set::BTreeSet<usize>) -> Option<usize> {
        st.range((Included(&x), Unbounded)).next().cloned()
    }
    fn add_tree(
        x: usize,
        par: usize,
        st: &mut btree_set::BTreeSet<usize>,
        doubling: &mut Vec<Vec<usize>>,
        depth: &mut Vec<usize>,
    ) {
        doubling[x][0] = par;
        for i in 0..(30 - 1) {
            doubling[x][i + 1] = doubling[doubling[x][i]][i];
        }
        st.insert(x);
        depth[x] = depth[par] + 1;
        //println!("{},{}",x,par);
    }
    fn get_lca(
        x: usize,
        y: usize,
        depth: &Vec<usize>,
        doubling: &Vec<Vec<usize>>,
    ) -> usize {
        let mut lowdepth = depth[x];
        let mut low = x;
        let mut updepth = depth[y];
        let mut up = y;
        if lowdepth > updepth {
            std::mem::swap(&mut lowdepth, &mut updepth);
            std::mem::swap(&mut low, &mut up);
        }
        for i in (0..30).rev() {
            if updepth - lowdepth >= (2u64).pow(i) as usize {
                updepth -= (2i64).pow(i) as usize;
                up = doubling[up][i as usize];
            }
        }
        //println!("up:low,updepath,lowdepth,{},{},{},{}",up,low,updepth,lowdepth);
        if up == low {
            return up;
        }
        for i in (0..30).rev() {
            if updepth - lowdepth > (2u64).pow(i as u32) as usize {
                if doubling[low][i] != doubling[up][i] {
                    low = doubling[low][i];
                    up = doubling[up][i];
                }
            }
        }
        doubling[low][0]
    }
    fn sub(
        x: usize,
        st: &mut btree_set::BTreeSet<usize>,
        doubling: &mut Vec<Vec<usize>>,
        depth: &mut Vec<usize>,
    ) {
        let l = get_below_max(x, &st);
        let r = get_above_min(x, &st);
        match (l, r) {
            (Some(l), Some(r)) => {
                let lca = get_lca(l, r, depth, doubling);
                //println!("{:?}",st);
                //println!("l:{:?},r:{:?},lca:{},x:{}",l,r,lca,x);
                if x < lca {
                    add_tree(x, l, st, doubling, depth);
                } else {
                    add_tree(x, r, st, doubling, depth);
                }
            }
            (Some(l), None) => {
                add_tree(x, l, st, doubling, depth);
            }
            (None, Some(r)) => {
                add_tree(x, r, st, doubling, depth);
            }
            (None, None) => {
                add_tree(x, 0, st, doubling, depth);
            }
        }
    }
    let mut doubling = vec![vec![0 as usize; 30]; n + 1];
    for i in v.clone(){
        sub(i, &mut st, &mut doubling, &mut depth);
    }
    for i in 0..n {
        print!("{} ",depth[v[i]]-1);
    }
    println!();
    let mut graph:Vec<Vec<usize>> = vec![vec![];n+1];
    for i in 0..n {
        graph[doubling[i+1][0]].push(i+1);
    }
    let mut sub_tree_size :Vec<usize>= vec![0;n+1];
    fn dfs(cur:usize,size:&mut Vec<usize>,graph:&Vec<Vec<usize>>) -> usize{
        size[cur] = 1;
        for to in &graph[cur] {
            size[cur] += dfs(to.clone(),size,graph);
        }
        return size[cur];
    }
    dfs(0,&mut sub_tree_size,&graph);
    for i in &v {
        print!("{} ",sub_tree_size[*i]-1);
    }
    println!();
}
0