結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 14:41:15 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 590 ms / 3,000 ms |
コード長 | 3,617 bytes |
コンパイル時間 | 17,278 ms |
コンパイル使用メモリ | 377,592 KB |
実行使用メモリ | 21,248 KB |
最終ジャッジ日時 | 2024-12-27 02:30:27 |
合計ジャッジ時間 | 38,087 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
pub mod chminmax {pub fn chmin<T: Copy + Ord>(a: &mut T, b: &T) -> bool {if *a > *b {*a = *b;true} else {false}}pub fn chmax<T: Copy + Ord>(a: &mut T, b: &T) -> bool {if *a < *b {*a = *b;true} else {false}}}pub mod lower_bound {pub fn lower_bound<T: Ord>(list: &[T], val: &T) -> usize {let mut l = 0;let mut r = list.len();while l < r {let x = (l + r) / 2;match list[x].cmp(val) {std::cmp::Ordering::Less => {l = x + 1;}std::cmp::Ordering::Equal | std::cmp::Ordering::Greater => {r = x;}}}l}pub fn upper_bound<T: Ord>(list: &[T], val: &T) -> usize {let mut l = 0;let mut r = list.len();while l < r {let x = (l + r) / 2;match list[x].cmp(val) {std::cmp::Ordering::Less | std::cmp::Ordering::Equal => {l = x + 1;}std::cmp::Ordering::Greater => {r = x;}}}l}}pub mod scanner {pub struct Scanner {buf: Vec<String>,}impl Scanner {pub fn new() -> Self {Self { buf: vec![] }}pub fn new_from(source: &str) -> Self {let source = String::from(source);let buf = Self::split(source);Self { buf }}pub fn next<T: std::str::FromStr>(&mut self) -> T {loop {if let Some(x) = self.buf.pop() {return x.parse().ok().expect("");}let mut source = String::new();std::io::stdin().read_line(&mut source).expect("");self.buf = Self::split(source);}}fn split(source: String) -> Vec<String> {source.split_whitespace().rev().map(String::from).collect::<Vec<_>>()}}}use std::collections::VecDeque;use crate::{chminmax::chmax, lower_bound::upper_bound, scanner::Scanner};fn main() {let mut scanner = Scanner::new();let t: usize = 1;for _ in 0..t {solve(&mut scanner);}}fn solve(scanner: &mut Scanner) {let n: usize = scanner.next();let mut g = vec![vec![]; n];for v in 2..=n {let l: usize = scanner.next();let u: usize = scanner.next();g[u - 1].push((v - 1, l));}let mut que = VecDeque::new();que.push_back(0);let mut res1: Vec<(usize, usize)> = vec![(1, 1)];let mut res2: Vec<isize> = vec![-1; n];res2[0] = 1;while let Some(u) = que.pop_front() {for &(v, l) in g[u].iter() {if res2[u] == -1 {continue;}let now = l.max(res2[u] as usize) as isize;chmax(&mut res2[v], &now);res1.push((res2[v] as usize, v));que.push_back(v);}}res1.sort();let q: usize = scanner.next();for _ in 0..q {let t: usize = scanner.next();if t == 1 {let x: usize = scanner.next();println!("{}", upper_bound(&res1, &(x, !0)));} else {let y: usize = scanner.next();println!("{}", res2[y - 1]);}}}