結果
| 問題 | No.2543 Many Meetings |
| ユーザー |
 haihamabossu
|
| 提出日時 | 2023-11-24 22:50:20 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 261 ms / 2,000 ms |
| コード長 | 7,871 bytes |
| コンパイル時間 | 13,903 ms |
| コンパイル使用メモリ | 390,272 KB |
| 実行使用メモリ | 125,128 KB |
| 最終ジャッジ日時 | 2024-09-26 09:43:13 |
| 合計ジャッジ時間 | 20,354 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
pub mod lowest_common_ancestor {pub struct LowestCommonAncestor {pub ancestor: Vec<Vec<Option<usize>>>,}impl LowestCommonAncestor {pub fn new(tree: &crate::tree::Tree) -> LowestCommonAncestor {let n = tree.n;let m = (n as f64).log2().ceil() as usize;let mut ancestor = vec![vec![None; m]; n];for u in 0..n {ancestor[u][0] = tree.parent[u];}for k in 1..m {for u in 0..n {if let Some(v) = ancestor[u][k - 1] {ancestor[u][k] = ancestor[v][k - 1];}}}LowestCommonAncestor { ancestor }}pub fn lca(&self, tree: &crate::tree::Tree, u: usize, v: usize) -> usize {let mut u = u;let mut v = v;if tree.depth[u] < tree.depth[v] {std::mem::swap(&mut u, &mut v);}let m = self.ancestor[0].len();for k in (0..m).rev() {if let Some(w) = self.ancestor[u][k] {if tree.depth[w] >= tree.depth[v] {u = w;}}}if u == v {return u;}for k in (0..m).rev() {if let (Some(pu), Some(pv)) = (self.ancestor[u][k], self.ancestor[v][k]) {if pu != pv {u = pu;v = pv;}}}self.ancestor[u][0].unwrap()}}}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<_>>()}}}pub mod tree {#[derive(Clone)]pub struct Edge {pub to: usize,pub id: usize,pub rev: usize,pub cost: isize,}pub struct Tree {pub n: usize,root: usize,pub edges: Vec<Vec<Edge>>,pub parent: Vec<Option<usize>>,pub depth: Vec<usize>,pub subtree_size: Vec<usize>,pub pre_order: Vec<usize>,pub post_order: Vec<usize>,pub euler_tour: Vec<usize>,}impl Tree {pub fn new(n: usize) -> Tree {Tree {n,root: 0,edges: vec![vec![]; n],parent: vec![None; n],depth: vec![0; n],subtree_size: vec![0; n],pre_order: vec![],post_order: vec![],euler_tour: vec![],}}pub fn init(scanner: &mut crate::scanner::Scanner, indexed: usize, weighted: bool) -> Tree {let n: usize = scanner.next();let mut tree = Tree::new(n);for id in 0..n - 1 {let u: usize = scanner.next::<usize>() - indexed;let v: usize = scanner.next::<usize>() - indexed;let cost: isize;if weighted {cost = scanner.next();} else {cost = 1;}tree.add_edge(u, v, id, cost);}tree.set_root(0);tree}pub fn add_edge(&mut self, u: usize, v: usize, id: usize, cost: isize) {{let to = v;let rev = self.edges[v].len();self.edges[u].push(Edge { to, id, rev, cost });}{let to = u;let rev = self.edges[u].len() - 1;self.edges[v].push(Edge { to, id, rev, cost });}}pub fn degree(&self, u: usize) -> usize {self.edges[u].len()}pub fn set_root(&mut self, root: usize) {let n = self.n;self.root = root;self.parent = vec![None; n];self.depth = vec![0; n];self.subtree_size = vec![0; n];self.pre_order = vec![];self.post_order = vec![];self.euler_tour = vec![];let mut stack: Vec<(usize, usize, usize)> = vec![];stack.push((root, 0, 0));while let Some((u, i, d)) = stack.pop() {if i == 0 {self.subtree_size[u] += 1;self.pre_order.push(u);}if i == self.degree(u) {if let Some(p) = self.parent[u] {self.subtree_size[p] += self.subtree_size[u];}self.post_order.push(u);self.euler_tour.push(u);continue;}stack.push((u, i + 1, d));let edge = &self.edges[u][i];if Some(edge.to) == self.parent[u] {continue;}self.parent[edge.to] = Some(u);self.depth[edge.to] = d + 1;self.euler_tour.push(u);stack.push((edge.to, 0, d + 1));}}}}use crate::{lowest_common_ancestor::LowestCommonAncestor, scanner::Scanner, tree::Tree};use std::{collections::VecDeque, io::Write};fn main() {let mut scanner = Scanner::new();let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());let t: usize = 1;for _ in 0..t {solve(&mut scanner, &mut out);}}const INF: usize = 1e10 as usize;fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {let n = scanner.next::<usize>();let k = scanner.next::<usize>();let mut lr = (0..n).map(|_| (scanner.next::<usize>(), scanner.next::<usize>())).collect::<Vec<_>>();lr.push((INF, INF + 1));lr.sort_by_cached_key(|a| (a.1, a.0));let mut que = VecDeque::new();let mut tree = Tree::new(n + 1);{let mut id = 0;for i in 0..n + 1 {let (l, r) = lr[i];while let Some(&(pr, pi)) = que.front() {if l < pr {break;}que.pop_front();tree.add_edge(i, pi, id, 1);id += 1;}que.push_back((r, i));}}tree.set_root(n);let lca = LowestCommonAncestor::new(&tree);let inf = 1e18 as usize;let mut ans = inf;for u in 0..n {if tree.depth[u] < k {continue;}let mut rem = k - 1;let mut j = 0;let mut v = u;while rem > 0 {if (rem & 1) == 1 {v = lca.ancestor[v][j].unwrap();}rem >>= 1;j += 1;}ans = ans.min(lr[v].1 - lr[u].0);}let ans = if ans == inf { -1 } else { ans as isize };writeln!(out, "{}", ans).unwrap();}