結果
| 問題 | No.1473 おでぶなおばけさん |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2021-04-09 23:08:53 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 88 ms / 2,000 ms |
| コード長 | 13,237 bytes |
| コンパイル時間 | 2,732 ms |
| コンパイル使用メモリ | 165,816 KB |
| 実行使用メモリ | 11,412 KB |
| 最終ジャッジ日時 | 2023-09-07 12:52:52 |
| 合計ジャッジ時間 | 5,652 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 46 ms
10,356 KB |
| testcase_03 | AC | 35 ms
9,060 KB |
| testcase_04 | AC | 35 ms
6,188 KB |
| testcase_05 | AC | 16 ms
4,384 KB |
| testcase_06 | AC | 59 ms
9,924 KB |
| testcase_07 | AC | 56 ms
11,412 KB |
| testcase_08 | AC | 88 ms
10,664 KB |
| testcase_09 | AC | 43 ms
10,664 KB |
| testcase_10 | AC | 22 ms
9,564 KB |
| testcase_11 | AC | 24 ms
9,864 KB |
| testcase_12 | AC | 21 ms
9,068 KB |
| testcase_13 | AC | 12 ms
6,444 KB |
| testcase_14 | AC | 10 ms
4,956 KB |
| testcase_15 | AC | 20 ms
10,020 KB |
| testcase_16 | AC | 15 ms
8,844 KB |
| testcase_17 | AC | 2 ms
4,380 KB |
| testcase_18 | AC | 3 ms
4,380 KB |
| testcase_19 | AC | 18 ms
7,048 KB |
| testcase_20 | AC | 27 ms
8,352 KB |
| testcase_21 | AC | 38 ms
9,112 KB |
| testcase_22 | AC | 17 ms
9,340 KB |
| testcase_23 | AC | 15 ms
7,992 KB |
| testcase_24 | AC | 16 ms
7,952 KB |
| testcase_25 | AC | 88 ms
9,376 KB |
| testcase_26 | AC | 35 ms
9,840 KB |
| testcase_27 | AC | 24 ms
4,776 KB |
| testcase_28 | AC | 40 ms
10,284 KB |
| testcase_29 | AC | 30 ms
8,620 KB |
| testcase_30 | AC | 43 ms
10,532 KB |
| testcase_31 | AC | 35 ms
11,124 KB |
| testcase_32 | AC | 34 ms
10,908 KB |
| testcase_33 | AC | 21 ms
9,812 KB |
| testcase_34 | AC | 9 ms
4,860 KB |
| testcase_35 | AC | 14 ms
5,688 KB |
| testcase_36 | AC | 35 ms
7,772 KB |
| testcase_37 | AC | 23 ms
7,768 KB |
| testcase_38 | AC | 3 ms
4,380 KB |
| testcase_39 | AC | 16 ms
8,900 KB |
| testcase_40 | AC | 17 ms
8,988 KB |
| testcase_41 | AC | 13 ms
10,048 KB |
| testcase_42 | AC | 14 ms
9,096 KB |
| testcase_43 | AC | 14 ms
9,716 KB |
| testcase_44 | AC | 15 ms
9,816 KB |
| testcase_45 | AC | 14 ms
9,760 KB |
| testcase_46 | AC | 24 ms
9,452 KB |
| testcase_47 | AC | 28 ms
11,056 KB |
| testcase_48 | AC | 27 ms
8,552 KB |
ソースコード
#![allow(unused_imports, unused_macros)]
use kyoproio::*;
use std::{
collections::*,
io::{self, prelude::*},
iter, mem,
};
fn run<I: Input, O: Write>(mut kin: I, mut out: O) {
let (n, m): (usize, usize) = kin.parse();
let mut g = LabeledGraph::<i32>::builder(n + 1);
g.extend_bi_edges(kin.parse_iter().take(m));
let g = g.build();
let mut l = 0;
let mut r = 1e9 as i32 + 1;
let mut min = 0;
let mut que = VecDeque::new();
let mut dist = vec![0; n + 1];
while r - l > 1 {
let h = (l + r) / 2;
que.clear();
que.push_back(1);
for d in &mut dist {
*d = 1 << 29;
}
dist[1] = 0;
while let Some(u) = que.pop_front() {
if u == n {
break;
}
for &(v, d) in &g[u] {
if h <= d && dist[v] >= 1 << 29 {
dist[v] = dist[u] + 1;
que.push_back(v);
}
}
}
if dist[n] < 1 << 29 {
min = dist[n];
l = h;
} else {
r = h;
}
}
wln!(out, "{} {}", l, min);
}
use std::{fmt, mem::ManuallyDrop, ops};
pub struct Graph(LabeledGraph<()>);
impl Graph {
pub fn builder(n: usize) -> GraphBuilder {
GraphBuilder(LabeledGraph::builder(n))
}
pub fn len(&self) -> usize {
self.0.len()
}
pub fn edges(&self) -> Edges {
Edges(self.0.edges())
}
}
impl ops::Index<usize> for Graph {
type Output = [usize];
fn index(&self, u: usize) -> &Self::Output {
// https://rust-lang.github.io/unsafe-code-guidelines/layout/structs-and-tuples.html#structs-with-1-zst-fields
unsafe { &*(self.0.index(u) as *const _ as *const _) }
}
}
impl ops::IndexMut<usize> for Graph {
fn index_mut(&mut self, u: usize) -> &mut Self::Output {
unsafe { &mut *(self.0.index_mut(u) as *mut _ as *mut _) }
}
}
impl fmt::Debug for Graph {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map()
.entries((0..self.len()).map(|u| (u, &self[u])))
.finish()
}
}
pub struct Edges<'a>(LabeledEdges<'a, ()>);
impl<'a> Iterator for Edges<'a> {
type Item = (usize, usize);
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(u, v, _)| (u, v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
pub struct GraphBuilder(LabeledGraphBuilder<()>);
impl GraphBuilder {
pub fn edge(&mut self, u: usize, v: usize) {
self.0.edge(u, v, ());
}
pub fn bi_edge(&mut self, u: usize, v: usize) {
self.0.bi_edge(u, v, ());
}
pub fn extend_bi_edges<I: IntoIterator<Item = (usize, usize)>>(&mut self, iter: I) {
self.0
.extend_bi_edges(iter.into_iter().map(|(u, v)| (u, v, ())))
}
pub fn build(self) -> Graph {
Graph(self.0.build())
}
}
impl Extend<(usize, usize)> for GraphBuilder {
fn extend<I: IntoIterator<Item = (usize, usize)>>(&mut self, iter: I) {
self.0.extend(iter.into_iter().map(|(u, v)| (u, v, ())))
}
}
pub struct LabeledGraph<T> {
edges: Box<[(usize, T)]>,
heads: Box<[usize]>,
}
impl<T> LabeledGraph<T> {
pub fn builder(n: usize) -> LabeledGraphBuilder<T> {
LabeledGraphBuilder {
nodes: Vec::new(),
heads: vec![!0; n],
}
}
pub fn len(&self) -> usize {
self.heads.len() - 1
}
pub fn edges(&self) -> LabeledEdges<T> {
LabeledEdges {
g: self,
u: 0,
i: 0,
}
}
}
impl<T> ops::Index<usize> for LabeledGraph<T> {
type Output = [(usize, T)];
fn index(&self, u: usize) -> &Self::Output {
&self.edges[self.heads[u]..self.heads[u + 1]]
}
}
impl<T> ops::IndexMut<usize> for LabeledGraph<T> {
fn index_mut(&mut self, u: usize) -> &mut Self::Output {
&mut self.edges[self.heads[u]..self.heads[u + 1]]
}
}
impl<T: fmt::Debug> fmt::Debug for LabeledGraph<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map()
.entries((0..self.len()).map(|u| (u, &self[u])))
.finish()
}
}
pub struct LabeledEdges<'a, T> {
g: &'a LabeledGraph<T>,
u: usize,
i: usize,
}
impl<'a, T> Iterator for LabeledEdges<'a, T> {
type Item = (usize, usize, &'a T);
fn next(&mut self) -> Option<Self::Item> {
let (v, l) = self.g.edges.get(self.i)?;
while self.g.heads[self.u + 1] == self.i {
self.u += 1;
}
self.i += 1;
Some((self.u, *v, l))
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.g.edges.len();
(len, Some(len))
}
}
pub struct LabeledGraphBuilder<T> {
nodes: Vec<(usize, ManuallyDrop<T>, usize)>,
heads: Vec<usize>,
}
impl<T> LabeledGraphBuilder<T> {
pub fn edge(&mut self, u: usize, v: usize, l: T) {
self.nodes.push((v, ManuallyDrop::new(l), self.heads[u]));
self.heads[u] = self.nodes.len() - 1;
}
pub fn bi_edge(&mut self, u: usize, v: usize, l: T)
where
T: Clone,
{
self.edge(u, v, l.clone());
self.edge(v, u, l);
}
pub fn extend_bi_edges<I: IntoIterator<Item = (usize, usize, T)>>(&mut self, iter: I)
where
T: Clone,
{
for (u, v, l) in iter {
self.bi_edge(u, v, l);
}
}
pub fn build(mut self) -> LabeledGraph<T> {
let mut edges = Vec::with_capacity(self.nodes.len());
let mut heads = Vec::with_capacity(self.heads.len() + 1);
for &(mut h) in &self.heads {
heads.push(edges.len());
while let Some((v, l, next)) = self.nodes.get_mut(h) {
unsafe {
edges.push((*v, ManuallyDrop::take(l)));
}
h = *next;
}
}
heads.push(edges.len());
LabeledGraph {
edges: edges.into(),
heads: heads.into(),
}
}
}
impl<T> Extend<(usize, usize, T)> for LabeledGraphBuilder<T> {
fn extend<I: IntoIterator<Item = (usize, usize, T)>>(&mut self, iter: I) {
for (u, v, l) in iter {
self.edge(u, v, l);
}
}
}
// -----------------------------------------------------------------------------
fn main() -> io::Result<()> {
std::thread::Builder::new()
.stack_size(1 << 26)
.spawn(|| {
run(
Scanner::new(io::stdin().lock()),
io::BufWriter::new(io::stdout().lock()),
)
})?
.join()
.unwrap();
Ok(())
}
#[macro_export]
macro_rules! w {
($($arg:tt)*) => { write!($($arg)*).unwrap(); }
}
#[macro_export]
macro_rules! wln {
($dst:expr $(, $($arg:tt)*)?) => {{
writeln!($dst $(, $($arg)*)?).unwrap();
#[cfg(debug_assertions)]
$dst.flush().unwrap();
}}
}
#[macro_export]
macro_rules! w_iter {
($dst:expr, $fmt:expr, $iter:expr, $delim:expr) => {{
let mut first = true;
for elem in $iter {
if first {
w!($dst, $fmt, elem);
first = false;
} else {
w!($dst, concat!($delim, $fmt), elem);
}
}
}};
($dst:expr, $fmt:expr, $iter:expr) => {
w_iter!($dst, $fmt, $iter, " ")
};
}
#[macro_export]
macro_rules! w_iter_ln {
($dst:expr, $($t:tt)*) => {{
w_iter!($dst, $($t)*);
wln!($dst);
}}
}
#[macro_export]
macro_rules! e {
($($t:tt)*) => {
#[cfg(debug_assertions)]
eprint!($($t)*)
}
}
#[macro_export]
macro_rules! eln {
($($t:tt)*) => {
#[cfg(debug_assertions)]
eprintln!($($t)*)
}
}
#[macro_export]
macro_rules! __tstr {
($h:expr $(, $t:expr)+) => { concat!(__tstr!($($t),+) , ", {} = {:?}") };
($h:expr) => { "[{}:{}] {} = {:?}" };
() => { "[{}:{}]" }
}
#[macro_export]
macro_rules! d {
($($a:expr),*) => { eln!(__tstr!($($a),*), file!(), line!(), $(stringify!($a), $a),*) };
}
pub mod kyoproio {
use std::{
fmt::Display,
io::{self, prelude::*},
iter::FromIterator,
marker::PhantomData,
mem::{self, MaybeUninit},
str,
};
pub trait Input {
fn bytes(&mut self) -> &[u8];
fn str(&mut self) -> &str {
str::from_utf8(self.bytes()).unwrap()
}
fn parse<T: Parse>(&mut self) -> T {
T::parse(self)
}
fn parse_iter<T: Parse>(&mut self) -> ParseIter<T, Self> {
ParseIter(self, PhantomData)
}
fn collect<T: Parse, B: FromIterator<T>>(&mut self, n: usize) -> B {
self.parse_iter().take(n).collect()
}
fn map<T: Parse, U, F: FnMut(T) -> U, B: FromIterator<U>>(&mut self, n: usize, f: F) -> B {
self.parse_iter().take(n).map(f).collect()
}
}
impl<I: Input> Input for &mut I {
fn bytes(&mut self) -> &[u8] {
(**self).bytes()
}
}
pub struct Scanner<R> {
src: R,
buf: Vec<u8>,
pos: usize,
len: usize,
}
impl<R: Read> Scanner<R> {
pub fn new(src: R) -> Self {
Self {
src,
buf: vec![0; 1 << 16],
pos: 0,
len: 0,
}
}
fn read(&mut self) -> usize {
if self.pos > 0 {
self.buf.copy_within(self.pos..self.len, 0);
self.len -= self.pos;
self.pos = 0;
} else if self.len >= self.buf.len() {
self.buf.resize(2 * self.buf.len(), 0);
}
let n = self.src.read(&mut self.buf[self.len..]).unwrap();
self.len += n;
assert!(self.len <= self.buf.len());
n
}
}
impl<R: Read> Input for Scanner<R> {
fn bytes(&mut self) -> &[u8] {
loop {
while let Some(d) = unsafe { self.buf.get_unchecked(self.pos..self.len) }
.iter()
.position(u8::is_ascii_whitespace)
{
let p = self.pos;
self.pos += d + 1;
if d > 0 {
return unsafe { self.buf.get_unchecked(p..p + d) };
}
}
if self.read() == 0 {
let p = self.pos;
self.pos = self.len;
return unsafe { self.buf.get_unchecked(p..self.len) };
}
}
}
}
pub struct ParseIter<'a, T, I: ?Sized>(&'a mut I, PhantomData<*const T>);
impl<'a, T: Parse, I: Input + ?Sized> Iterator for ParseIter<'a, T, I> {
type Item = T;
fn next(&mut self) -> Option<T> {
Some(self.0.parse())
}
fn size_hint(&self) -> (usize, Option<usize>) {
(!0, None)
}
}
pub trait Parse: Sized {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self;
}
impl Parse for Vec<u8> {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self {
src.bytes().to_owned()
}
}
macro_rules! from_str {
($($T:ty)*) => {$(
impl Parse for $T {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self {
src.str().parse::<$T>().unwrap()
}
}
)*}
}
from_str!(String char bool f32 f64);
macro_rules! int {
($($I:ty: $U:ty)*) => {$(
impl Parse for $I {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self {
let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $I);
let s = src.bytes();
if let Some((&b'-', t)) = s.split_first() { -f(t) } else { f(s) }
}
}
impl Parse for $U {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self {
src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $U)
}
}
)*}
}
int!(isize:usize i8:u8 i16:u16 i32:u32 i64:u64 i128:u128);
macro_rules! tuple {
($H:ident $($T:ident)*) => {
impl<$H: Parse, $($T: Parse),*> Parse for ($H, $($T),*) {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self {
($H::parse(src), $($T::parse(src)),*)
}
}
tuple!($($T)*);
};
() => {}
}
tuple!(A B C D E F G);
macro_rules! array {
($($N:literal)*) => {$(
impl<T: Parse> Parse for [T; $N] {
fn parse<I: Input + ?Sized>(src: &mut I) -> Self {
unsafe {
let mut arr: [MaybeUninit<T>; $N] = MaybeUninit::uninit().assume_init();
for elem in &mut arr {
*elem = MaybeUninit::new(src.parse());
}
mem::transmute_copy(&arr)
}
}
}
)*}
}
array!(1 2 3 4 5 6 7 8);
}