結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2018-12-27 15:01:45 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 2,744 bytes |
コンパイル時間 | 14,585 ms |
コンパイル使用メモリ | 384,140 KB |
実行使用メモリ | 25,612 KB |
最終ジャッジ日時 | 2024-10-14 01:53:52 |
合計ジャッジ時間 | 14,285 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#![allow(unused_imports)]use std::io::{ self, Write };use std::str::FromStr;use std::cmp::{ min, max };use std::collections::{ BinaryHeap, VecDeque };#[allow(unused_macros)]macro_rules! trace {($var:expr) => {let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);};($($args:expr),*) => { trace!(($($args),*)) }}#[allow(unused_macros)]macro_rules! put {($var:expr) => {let _ = writeln!(&mut std::io::stdout(), "{}", $var);};($var:expr, $($args:expr),*) => {let _ = write!(&mut std::io::stdout(), "{} ", $var);put!($($args),*);};}use std::ops::Range;struct BIT { size: usize, array: Vec<i32> }#[allow(dead_code)]impl BIT {fn new(n: usize) -> BIT {BIT { size: n, array: vec![0; n + 1] }}fn add(&mut self, idx: usize, w: i32) {let mut x = idx + 1;while x <= self.size {self.array[x] += w;let xi = x as i32;x += (xi&-xi) as usize;}}fn sum_up(&self, idx: usize) -> i32 { // [0, idx)let mut sum = 0;let mut x = idx;while x > 0 {sum += self.array[x];let xi = x as i32;x -= (xi&-xi) as usize;}sum}fn sum(&self, range: Range<usize>) -> i32 {self.sum_up(range.end) - self.sum_up(range.start)}}fn main() {let mut sc = Scanner::new();let n: usize = sc.cin();let mut bit = BIT::new(n);let mut tree = vec![vec![]; n];for i in 1..n {let a: usize = sc.cin();tree[a].push(i);}let mut stack = vec![(true, 0)];let mut ans = 0u64;while let Some((dir, u)) = stack.pop() {if dir {ans += bit.sum_up(u) as u64;bit.add(u, 1);stack.push((false, u));for &v in tree[u].iter() {stack.push((true, v));}} else {bit.add(u, -1);}}put!(ans);}#[allow(dead_code)]struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }#[allow(dead_code)]impl Scanner {fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }fn reserve(&mut self) {while self.buffer.len() == 0 {let mut line = String::new();let _ = self.stdin.read_line(&mut line);for w in line.split_whitespace() {self.buffer.push_back(String::from(w));}}}fn cin<T: FromStr>(&mut self) -> T {self.reserve();match self.buffer.pop_front().unwrap().parse::<T>() {Ok(a) => a,Err(_) => panic!("parse err")}}}