#992677 (Rust) No.1069 電柱 / Pole (Hard)

提出ソース

結果

問題	No.1069 電柱 / Pole (Hard)
ユーザー	Haar
提出日時	2024-07-04 19:12:18
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	113 ms / 2,000 ms
コード長	17,252 bytes
コンパイル時間	17,512 ms
コンパイル使用メモリ	378,212 KB
実行使用メモリ	16,128 KB
最終ジャッジ日時	2024-07-04 19:12:41
合計ジャッジ時間	20,926 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	113 ms 7,936 KB
testcase_05	AC	99 ms 16,128 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	5 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	5 ms 5,376 KB
testcase_20	AC	1 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	9 ms 5,376 KB
testcase_24	AC	5 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	3 ms 5,376 KB
testcase_27	AC	3 ms 5,376 KB
testcase_28	AC	4 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	AC	1 ms 5,376 KB
testcase_34	AC	1 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	0 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	2 ms 5,376 KB
testcase_44	AC	3 ms 5,376 KB
testcase_45	AC	2 ms 5,376 KB
testcase_46	AC	4 ms 5,376 KB
testcase_47	AC	4 ms 5,376 KB
testcase_48	AC	4 ms 5,376 KB
testcase_49	AC	3 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	4 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	4 ms 5,376 KB
testcase_54	AC	1 ms 5,376 KB
testcase_55	AC	1 ms 5,376 KB
testcase_56	AC	1 ms 5,376 KB
testcase_57	AC	1 ms 5,376 KB
testcase_58	AC	1 ms 5,376 KB
testcase_59	AC	1 ms 5,376 KB
testcase_60	AC	1 ms 5,376 KB
testcase_61	AC	1 ms 5,376 KB
testcase_62	AC	1 ms 5,376 KB
testcase_63	AC	1 ms 5,376 KB
testcase_64	AC	1 ms 5,376 KB
testcase_65	AC	1 ms 5,376 KB
testcase_66	AC	1 ms 5,376 KB
testcase_67	AC	1 ms 5,376 KB
testcase_68	AC	1 ms 5,376 KB
testcase_69	AC	2 ms 5,376 KB
testcase_70	AC	1 ms 5,376 KB
testcase_71	AC	2 ms 5,376 KB
testcase_72	AC	1 ms 5,376 KB
testcase_73	AC	2 ms 5,376 KB
testcase_74	AC	2 ms 5,376 KB
testcase_75	AC	2 ms 5,376 KB
testcase_76	AC	4 ms 5,376 KB
testcase_77	AC	4 ms 5,376 KB
testcase_78	AC	2 ms 5,376 KB
testcase_79	AC	4 ms 5,376 KB
testcase_80	AC	4 ms 5,376 KB
testcase_81	AC	3 ms 5,376 KB
testcase_82	AC	3 ms 5,376 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused import: `utils::join_str::*`
  --> src/main.rs:11:9
   |
11 |         utils::join_str::*,
   |         ^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

ソースコード

raw source code

// Bundled at 2024/07/04 19:11:45 +09:00
// Author: Haar

pub mod main {
    use super::*;
    use haar_lib::{
        get,
        graph::{yen::*, *},
        input,
        utils::fastio::*,
        utils::join_str::*,
        utils::total_f64::*,
    };
    #[allow(unused_imports)]
    use std::cell::RefCell;
    #[allow(unused_imports)]
    use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
    #[allow(unused_imports)]
    use std::io::Write;
    #[allow(unused_imports)]
    use std::rc::Rc;
    #[derive(Clone, Default)]
    pub struct Problem {}
    impl Problem {
        pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
            let mut io = FastIO::new();
            input!(io >> n: usize, m: usize, k: usize);
            let x = io.read_usize() - 1;
            let y = io.read_usize() - 1;
            let mut ps = vec![];
            let mut qs = vec![];
            for _ in 0..n {
                ps.push(io.read_i64());
                qs.push(io.read_i64());
            }
            let mut g = Graph::<Undirected, _>::new(n);
            for _ in 0..m {
                let p = io.read_usize() - 1;
                let q = io.read_usize() - 1;
                let dx = (ps[p] - ps[q]) as f64;
                let dy = (qs[p] - qs[q]) as f64;
                let l = (dx * dx + dy * dy).sqrt();
                g.add(Edge::new(p, q, Totalf64(l), ()));
            }
            let ans = yen_algorithm(&g, x, y, k);
            for a in ans {
                if let Some((Totalf64(a), _)) = a {
                    io.writeln(a);
                } else {
                    io.writeln(-1);
                }
            }
            Ok(())
        }
    }
}
fn main() {
    main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod graph {
    pub mod yen {
        use crate::trait_alias;
        use crate::{graph::*, traits::one_zero::Zero};
        use std::ops::{Add, AddAssign};
        use std::{cmp::Reverse, collections::BinaryHeap};
        trait_alias!(
            Elem,
            Zero<Output = Self> + Add<Output = Self> + AddAssign + Ord + Eq + Copy
        );
        type Path = Vec<usize>;
        fn shortest_path<D: Direction, T: Elem, E: EdgeTrait<Weight = T>>(
            g: &Graph<D, E>,
            from: usize,
            t: usize,
            usable: &Vec<bool>,
            valid: &Vec<Vec<bool>>,
        ) -> Option<(T, Path)> {
            let n = g.len();
            let mut visited = vec![false; n];
            let mut dist = vec![None; n];
            let mut restore = vec![(0, 0); n];
            let mut pq = BinaryHeap::<Reverse<(T, usize)>>::new();
            dist[from] = Some(T::zero());
            pq.push(Reverse((T::zero(), from)));
            while let Some(Reverse((d, i))) = pq.pop() {
                if visited[i] {
                    continue;
                }
                visited[i] = true;
                for (k, e) in g.edges[i].iter().enumerate() {
                    if !valid[i][k] || !usable[e.to()] {
                        continue;
                    }
                    if dist[e.to()].is_none() || dist[e.to()].unwrap() > d + e.weight() {
                        dist[e.to()] = Some(d + e.weight());
                        restore[e.to()] = (i, k);
                        if !visited[e.to()] {
                            pq.push(Reverse((dist[e.to()].unwrap(), e.to())));
                        }
                    }
                }
            }
            if let Some(d) = dist[t] {
                let mut p = vec![];
                let mut cur = t;
                while cur != from {
                    let (i, j) = restore[cur];
                    p.push(j);
                    cur = i;
                }
                p.reverse();
                Some((d, p))
            } else {
                None
            }
        }
        pub fn yen_algorithm<D: Direction, T: Elem, E: EdgeTrait<Weight = T>>(
            g: &Graph<D, E>,
            s: usize,
            t: usize,
            k: usize,
        ) -> Vec<Option<(T, Path)>> {
            let n = g.len();
            let mut valid = vec![vec![]; n];
            let mut result: Vec<Option<(T, Path)>> = vec![None; k];
            let mut stock = BinaryHeap::<Reverse<(T, Path)>>::new();
            for i in 0..n {
                valid[i] = vec![true; g.edges[i].len()];
            }
            for i in 0..k {
                if i == 0 {
                    let usable = vec![true; n];
                    if let Some((c, p)) = shortest_path(g, s, t, &usable, &valid) {
                        stock.push(Reverse((c, p)));
                    }
                } else {
                    let mut prev_path = vec![];
                    let mut cur = s;
                    for &u in &result[i - 1].as_ref().unwrap().1 {
                        prev_path.push(cur);
                        cur = g.edges[cur][u].to();
                    }
                    prev_path.push(t);
                    let mut check = vec![true; i];
                    let mut usable = vec![true; n];
                    for k in 0..prev_path.len() - 1 {
                        let u = prev_path[k];
                        for j in 0..i {
                            if check[j] {
                                valid[prev_path[k]][result[j].as_ref().unwrap().1[k]] = false;
                            }
                        }
                        if let Some((mut c, p)) = shortest_path(g, u, t, &usable, &valid) {
                            let mut temp = vec![];
                            for j in 0..k {
                                let v = result[i - 1].as_ref().unwrap().1[j];
                                c += g.edges[prev_path[j]][v].weight();
                                temp.push(v);
                            }
                            temp.extend(p.into_iter());
                            stock.push(Reverse((c, temp)));
                        }
                        usable[u] = false;
                        for j in 0..i {
                            if check[j] {
                                valid[prev_path[k]][result[j].as_ref().unwrap().1[k]] = true;
                            }
                        }
                        for j in 0..i {
                            if check[j] {
                                if prev_path[k + 1]
                                    != g.edges[prev_path[k]][result[j].as_ref().unwrap().1[k]].to()
                                {
                                    check[j] = false;
                                }
                            }
                        }
                    }
                }
                if stock.is_empty() {
                    break;
                }
                result[i] = stock.pop().map(|Reverse((c, p))| (c, p));
                while stock.peek().map(|Reverse((c, p))| (*c, p.clone())) == result[i] {
                    stock.pop();
                }
            }
            result
        }
    }
    use std::marker::PhantomData;
    pub trait EdgeTrait {
        type Weight;
        fn from(&self) -> usize;
        fn to(&self) -> usize;
        fn weight(&self) -> Self::Weight;
        fn rev(self) -> Self;
    }
    #[derive(Debug, Clone)]
    pub struct Edge<T, I> {
        pub from: usize,
        pub to: usize,
        pub weight: T,
        pub index: I,
    }
    impl<T, I> Edge<T, I> {
        pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
            Self {
                from,
                to,
                weight,
                index,
            }
        }
    }
    impl<T: Clone, I> EdgeTrait for Edge<T, I> {
        type Weight = T;

        #[inline]

        fn from(&self) -> usize {
            self.from
        }

        #[inline]

        fn to(&self) -> usize {
            self.to
        }

        #[inline]

        fn weight(&self) -> Self::Weight {
            self.weight.clone()
        }

        fn rev(mut self) -> Self {
            std::mem::swap(&mut self.from, &mut self.to);
            self
        }
    }
    pub trait Direction {}
    #[derive(Debug, Clone)]
    pub struct Directed;
    #[derive(Debug, Clone)]
    pub struct Undirected;
    impl Direction for Directed {}
    impl Direction for Undirected {}
    #[derive(Debug, Clone)]
    pub struct Graph<D, E> {
        pub edges: Vec<Vec<E>>,
        __phantom: PhantomData<D>,
    }
    impl<D: Direction, E: EdgeTrait + Clone> Graph<D, E> {
        pub fn new(size: usize) -> Self {
            Graph {
                edges: vec![vec![]; size],
                __phantom: PhantomData,
            }
        }
    }
    impl<E: EdgeTrait + Clone> Graph<Directed, E> {
        pub fn add(&mut self, e: E) {
            self.edges[e.from()].push(e);
        }

        pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
            edges.into_iter().for_each(|e| self.add(e));
        }
    }
    impl<E: EdgeTrait + Clone> Graph<Undirected, E> {
        pub fn add(&mut self, e: E) {
            self.edges[e.from()].push(e.clone());
            self.edges[e.to()].push(e.rev());
        }

        pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
            edges.into_iter().for_each(|e| self.add(e));
        }
    }
    impl<D, E> Graph<D, E> {
        pub fn len(&self) -> usize {
            self.edges.len()
        }

        pub fn is_empty(&self) -> bool {
            self.edges.is_empty()
        }
    }
}
pub mod macros {
    pub mod io {
        #[macro_export]
        macro_rules! get {
    ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
        {
            let n = $num;
            (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
        }
    };
    ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
        ($(get!($in, $type $(as $to)*)),*)
    };
    ( $in:ident, i8 ) => { $in.read_i64() as i8 };
    ( $in:ident, i16 ) => { $in.read_i64() as i16 };
    ( $in:ident, i32 ) => { $in.read_i64() as i32 };
    ( $in:ident, i64 ) => { $in.read_i64() };
    ( $in:ident, isize ) => { $in.read_i64() as isize };
    ( $in:ident, u8 ) => { $in.read_u64() as u8 };
    ( $in:ident, u16 ) => { $in.read_u64() as u16 };
    ( $in:ident, u32 ) => { $in.read_u64() as u32 };
    ( $in:ident, u64 ) => { $in.read_u64() };
    ( $in:ident, usize ) => { $in.read_u64() as usize };
    ( $in:ident, [char] ) => { $in.read_chars() };
    ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
        #[macro_export]
        macro_rules! input {
    ( @inner $in:ident, mut $name:ident : $type:tt ) => {
        let mut $name = get!($in, $type);
    };
    ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
        let mut $name = get!($in, $type as $to);
    };
    ( @inner $in:ident, $name:ident : $type:tt ) => {
        let $name = get!($in, $type);
    };
    ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
        let $name = get!($in, $type as $to);
    };
    ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
        $(input!(@inner $in, $($names)* : $type $(as $to)*);)*
    }
}
    }
    pub mod trait_alias {
        #[macro_export]
        macro_rules! trait_alias {
    ($name:ident, $($t:tt)+) => {
        pub trait $name : $($t)+ {}
        impl<T: $($t)+> $name for T {}
    }
}
    }
}
pub mod traits {
    pub mod one_zero {
        #[doc = " 加算についての単位元をもつ"]
        pub trait Zero {
            type Output;
            fn zero() -> Self::Output;
        }
        #[doc = " 乗算についての単位元をもつ"]
        pub trait One {
            type Output;
            fn one() -> Self::Output;
        }
        macro_rules! impl_one_zero {
    ($($t:ty),*) => {
        $(
            impl Zero for $t {
                type Output = $t;
                fn zero() -> Self::Output { 0 as $t }
            }
            impl One for $t {
                type Output = $t;
                fn one() -> Self::Output { 1 as $t }
            }
        )*
    }
}
        impl_one_zero!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, f32, f64);
    }
}
pub mod utils {
    pub mod fastio {
        use std::fmt::Display;
        use std::io::{Read, Write};
        pub struct FastIO {
            in_bytes: Vec<u8>,
            in_cur: usize,
            out_buf: std::io::BufWriter<std::io::Stdout>,
        }
        impl FastIO {
            pub fn new() -> Self {
                let mut s = vec![];
                std::io::stdin().read_to_end(&mut s).unwrap();
                let cout = std::io::stdout();
                Self {
                    in_bytes: s,
                    in_cur: 0,
                    out_buf: std::io::BufWriter::new(cout),
                }
            }

            #[inline]
            pub fn getc(&mut self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    self.in_cur += 1;
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }

            #[inline]
            pub fn peek(&self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }

            #[inline]
            pub fn skip(&mut self) {
                while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
                    self.in_cur += 1;
                }
            }

            pub fn read_u64(&mut self) -> u64 {
                self.skip();
                let mut ret: u64 = 0;
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
                    self.in_cur += 1;
                }
                ret
            }

            pub fn read_u32(&mut self) -> u32 {
                self.read_u64() as u32
            }

            pub fn read_usize(&mut self) -> usize {
                self.read_u64() as usize
            }

            pub fn read_i64(&mut self) -> i64 {
                self.skip();
                let mut ret: i64 = 0;
                let minus = if self.peek() == Some(b'-') {
                    self.in_cur += 1;
                    true
                } else {
                    false
                };
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
                    self.in_cur += 1;
                }
                if minus {
                    ret = -ret;
                }
                ret
            }

            pub fn read_i32(&mut self) -> i32 {
                self.read_i64() as i32
            }

            pub fn read_isize(&mut self) -> isize {
                self.read_i64() as isize
            }

            pub fn read_chars(&mut self) -> Vec<char> {
                self.skip();
                let mut ret = vec![];
                while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur] as char);
                    self.in_cur += 1;
                }
                ret
            }

            pub fn write<T: Display>(&mut self, s: T) {
                self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
            }

            pub fn writeln<T: Display>(&mut self, s: T) {
                self.write(s);
                self.out_buf.write_all(&[b'\n']).unwrap();
            }
        }
        impl Drop for FastIO {
            fn drop(&mut self) {
                self.out_buf.flush().unwrap();
            }
        }
    }
    pub mod join_str {
        pub trait JoinStr {
            fn join_str(self, _: &str) -> String;
        }
        impl<T, I> JoinStr for I
        where
            T: ToString,
            I: Iterator<Item = T>,
        {
            fn join_str(self, s: &str) -> String {
                self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
            }
        }
    }
    pub mod total_f64 {
        use crate::traits::one_zero::*;
        use std::{
            cmp::Ordering,
            ops::{Add, AddAssign},
        };
        #[derive(Clone, Copy, Debug, PartialOrd, PartialEq)]
        pub struct Totalf64(pub f64);
        impl Eq for Totalf64 {}
        impl Ord for Totalf64 {
            fn cmp(&self, other: &Self) -> Ordering {
                self.0.partial_cmp(&other.0).unwrap()
            }
        }
        impl Add for Totalf64 {
            type Output = Self;

            fn add(self, rhs: Self) -> Self::Output {
                Self(self.0 + rhs.0)
            }
        }
        impl AddAssign for Totalf64 {
            fn add_assign(&mut self, rhs: Self) {
                self.0 += rhs.0;
            }
        }
        impl Zero for Totalf64 {
            type Output = Self;

            fn zero() -> Self::Output {
                Totalf64(0.0)
            }
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード