結果
問題 | No.1244 Black Segment |
ユーザー |
|
提出日時 | 2020-10-07 08:51:57 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 3,399 bytes |
コンパイル時間 | 14,179 ms |
コンパイル使用メモリ | 400,300 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-07-20 03:15:26 |
合計ジャッジ時間 | 16,749 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#![allow(unused_imports)]use {std::cmp::*, std::collections::*, std::io::Write, std::ops::*};#[allow(unused_macros)]macro_rules !dbg {($($e :expr ) ,*) =>{#[cfg (debug_assertions ) ] $({let (e ,mut err ) =(stringify !($e ) ,std ::io ::stderr () ) ;writeln !(err,"{} = {:?}" ,e ,$e ) .unwrap () } ) *} ;}#[allow(unused_macros)]macro_rules !min {($a :expr $(,) *) =>{{$a } } ;($a :expr ,$b :expr $(,) *) =>{{std ::cmp ::min ($a ,$b ) } } ;($a :expr ,$($rest :expr ) ,+$(,) *)=>{{std ::cmp ::min ($a ,min !($($rest ) ,+) ) } } ;}#[allow(unused_macros)]macro_rules !chmin {($base :expr ,$($cmps :expr ) ,+$(,) *) =>{{let cmp_min =min !($($cmps ) ,+) ;if $base >cmp_min {$base =cmp_min ;true } else{false } } } ;}#[allow(unused_macros)]macro_rules !max {($a :expr $(,) *) =>{{$a } } ;($a :expr ,$b :expr $(,) *) =>{{std ::cmp ::max ($a ,$b ) } } ;($a :expr ,$($rest :expr ) ,+$(,) *)=>{{std ::cmp ::max ($a ,max !($($rest ) ,+) ) } } ;}#[allow(unused_macros)]macro_rules !chmax {($base :expr ,$($cmps :expr ) ,+$(,) *) =>{{let cmp_max =max !($($cmps ) ,+) ;if $base <cmp_max {$base =cmp_max ;true } else{false } } } ;}#[allow(dead_code)]mod scanner {use std;use std::io::Read;use std::str::FromStr;use std::str::SplitWhitespace;pub struct Scanner<'a> {it: SplitWhitespace<'a>,}impl<'a> Scanner<'a> {pub fn new(s: &'a String) -> Scanner<'a> {Scanner {it: s.split_whitespace(),}}pub fn next<T: FromStr>(&mut self) -> T {match self.it.next().unwrap().parse::<T>() {Ok(v) => v,_ => panic!("Scanner error"),}}pub fn next_chars(&mut self) -> Vec<char> {self.next::<String>().chars().collect()}pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {(0..len).map(|_| self.next()).collect()}}pub fn read_string() -> String {let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s}}fn main() {let sc = scanner::read_string();let mut sc = scanner::Scanner::new(&sc);let n: usize = sc.next();let m: usize = sc.next();let a: usize = sc.next();let b: usize = sc.next();let mut to = vec![vec![]; n + 2];for _ in 0..m {let mut l: usize = sc.next();let mut r: usize = sc.next();if l < a && r < a {continue;}if l > b && r > b {continue;}if l < a {l = a;}if r > b {r = b + 1;} else {r += 1;}to[l].push(r);to[r].push(l);}let mut d = vec![100000000usize; n + 2];let mut visited = vec![false; n + 2];let mut q = std::collections::VecDeque::<usize>::new();q.push_back(a);d[a] = 0;while let Some(v) = q.pop_front() {dbg!(v);if visited[v] {continue;}visited[v] = true;for &u in to[v].iter() {if visited[u] {continue;}dbg!((v, u));d[u] = min(d[u], d[v] + 1);q.push_back(u);}}if d[b + 1] <= m {println!("{}", d[b + 1]);} else {println!("-1");}}