#957044 (Rust) No.2674 k-Walk on Bipartite

提出ソース

結果

問題	No.2674 k-Walk on Bipartite
ユーザー	ngtkana
提出日時	2024-03-02 00:00:47
言語	Rust (1.77.0)
結果	AC
実行時間	145 ms / 2,000 ms
コード長	11,142 bytes
コンパイル時間	2,670 ms
コンパイル使用メモリ	196,892 KB
実行使用メモリ	18,860 KB
最終ジャッジ日時	2024-03-13 19:33:29
合計ジャッジ時間	5,497 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,548 KB
testcase_01	AC	1 ms 6,548 KB
testcase_02	AC	1 ms 6,548 KB
testcase_03	AC	0 ms 6,548 KB
testcase_04	AC	1 ms 6,548 KB
testcase_05	AC	1 ms 6,548 KB
testcase_06	AC	1 ms 6,548 KB
testcase_07	AC	76 ms 15,936 KB
testcase_08	AC	85 ms 13,056 KB
testcase_09	AC	66 ms 15,932 KB
testcase_10	AC	115 ms 15,216 KB
testcase_11	AC	69 ms 12,912 KB
testcase_12	AC	110 ms 13,568 KB
testcase_13	AC	56 ms 14,120 KB
testcase_14	AC	16 ms 9,996 KB
testcase_15	AC	130 ms 16,640 KB
testcase_16	AC	86 ms 16,860 KB
testcase_17	AC	72 ms 12,672 KB
testcase_18	AC	31 ms 10,496 KB
testcase_19	AC	68 ms 15,016 KB
testcase_20	AC	63 ms 15,360 KB
testcase_21	AC	89 ms 13,920 KB
testcase_22	AC	145 ms 18,860 KB
testcase_23	AC	1 ms 6,548 KB
testcase_24	AC	1 ms 6,548 KB
testcase_25	AC	1 ms 6,548 KB
testcase_26	AC	1 ms 6,548 KB
testcase_27	AC	1 ms 6,548 KB
testcase_28	AC	0 ms 6,548 KB
testcase_29	AC	1 ms 6,548 KB
testcase_30	AC	1 ms 6,548 KB
testcase_31	AC	1 ms 6,548 KB
testcase_32	AC	1 ms 6,548 KB
testcase_33	AC	1 ms 6,548 KB
testcase_34	AC	1 ms 6,548 KB
testcase_35	AC	1 ms 6,548 KB
testcase_36	AC	0 ms 6,548 KB
testcase_37	AC	1 ms 6,548 KB
testcase_38	AC	1 ms 6,548 KB

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

ソースコード

raw source code

use input::input_array;
use std::collections::VecDeque;
use union_find::UnionFind;

fn main() {
    let [n, m] = input_array::<usize, 2>();
    let [s, t, k] = input_array::<usize, 3>();
    let s = s - 1;
    let t = t - 1;
    let mut uf = UnionFind::<()>::new(2 * n);
    let mut g = vec![Vec::new(); n];
    for _ in 0..m {
        let [i, j] = input_array::<usize, 2>();
        let i = i - 1;
        let j = j - 1;
        g[i].push(j);
        g[j].push(i);
        uf.union(i, n + j);
        uf.union(j, n + i);
    }
    let dist = calc_dist(s, &g);
    let ans = if n == 1 {
        Ans::No
    }
    else if n == 2 {
        match m {
            0 => {
                if s == t {
                    match k % 2 {
                        0 => {
                            if k == 0 {
                                Ans::Yes
                            } else {
                                Ans::Unknown
                            }
                        }
                        1 => Ans::No,
                        _ => unreachable!(),
                    }
                } else {
                    match k % 2 {
                        0 => Ans::No,
                        1 => Ans::Unknown,
                        _ => unreachable!(),
                    }
                }
            }
            1 => {
                if s == t {
                    match k % 2 {
                        0 => Ans::Yes,
                        1 => Ans::No,
                        _ => unreachable!(),
                    }
                } else {
                    match k % 2 {
                        0 => Ans::No,
                        1 => Ans::Yes,
                        _ => unreachable!(),
                    }
                }
            }
            _ => unreachable!(),
        }
    }
    // disjoint
    else if !uf.same(s, t) && !uf.same(s, t + n) {
        Ans::Unknown
    }
    // same part
    else if uf.same(s, t) {
        match k % 2 {
            0 => {
                if k < dist[t] {
                    Ans::Unknown
                } else {
                    Ans::Yes
                }
            }
            1 => Ans::No,
            _ => unreachable!(),
        }
    }
    // other part
    else {
        match k % 2 {
            0 => Ans::No,
            1 => {
                if k < dist[t] {
                    Ans::Unknown
                } else {
                    Ans::Yes
                }
            }
            _ => unreachable!(),
        }
    };
    println!(
        "{}",
        match ans {
            Ans::Yes => "Yes",
            Ans::No => "No",
            Ans::Unknown => "Unknown",
        }
    );
}

#[derive(Clone, Copy)]
enum Ans {
    Yes,
    No,
    Unknown,
}
pub fn calc_dist(start: usize, g: &[Vec<usize>]) -> Vec<usize> {
    let mut dist = vec![std::usize::MAX; g.len()];
    dist[start] = 0;
    let mut queue = VecDeque::from(vec![start]);
    while let Some(x) = queue.pop_front() {
        for &y in &g[x] {
            if dist[y] == std::usize::MAX {
                dist[y] = dist[x] + 1;
                queue.push_back(y);
            }
        }
    }
    dist
}

// input {{{
#[allow(dead_code)]
mod input {
    use std::cell::Cell;
    use std::convert::TryFrom;
    use std::io::stdin;
    use std::io::BufRead;
    use std::io::BufReader;
    use std::io::Lines;
    use std::io::Stdin;
    use std::str::FromStr;
    use std::sync::Mutex;
    use std::sync::Once;
    type Server = Mutex<Lines<BufReader<Stdin>>>;
    static ONCE: Once = Once::new();
    pub struct Lazy(Cell<Option<Server>>);
    unsafe impl Sync for Lazy {}
    fn line() -> String {
        static SYNCER: Lazy = Lazy(Cell::new(None));
        ONCE.call_once(|| {
            SYNCER
                .0
                .set(Some(Mutex::new(BufReader::new(stdin()).lines())));
        });
        unsafe {
            (*SYNCER.0.as_ptr())
                .as_ref()
                .unwrap()
                .lock()
                .unwrap()
                .next()
                .unwrap()
                .unwrap()
        }
    }
    pub trait ForceFromStr: FromStr {
        fn force_from_str(s: &str) -> Self;
    }
    impl<T, E> ForceFromStr for T
    where
        T: FromStr<Err = E>,
        E: std::fmt::Debug,
    {
        fn force_from_str(s: &str) -> Self {
            s.parse().unwrap()
        }
    }
    pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
    where
        T: std::fmt::Debug,
    {
        <[_; N]>::try_from(input_vec()).unwrap()
    }
    pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
        line()
            .split_whitespace()
            .map(T::force_from_str)
            .collect::<Vec<_>>()
    }
    pub fn input<T: ForceFromStr>() -> T {
        T::force_from_str(&line())
    }
}
// }}}
// union_find {{{
#[allow(dead_code)]
mod union_find {
    use std::fmt::Debug;
    use std::fmt::Formatter;
    use std::fmt::Result;
    use std::iter::repeat_with;
    use std::marker::PhantomData;
    use std::mem::replace;
    use std::mem::swap;
    use std::mem::take;
    pub trait Op {
        type Value: Default;
        fn singleton() -> Self::Value;
        fn add_edge(x: &mut Self::Value);
        fn graft(parent: &mut Self::Value, child: Self::Value);
    }
    impl Op for () {
        type Value = ();

        fn singleton() -> Self::Value {}

        fn add_edge(_x: &mut Self::Value) {}

        fn graft(_parent: &mut Self::Value, _child: Self::Value) {}
    }
    impl<T: Op, U: Op> Op for (T, U) {
        type Value = (T::Value, U::Value);

        fn singleton() -> Self::Value {
            (T::singleton(), U::singleton())
        }

        fn add_edge(x: &mut Self::Value) {
            T::add_edge(&mut x.0);
            U::add_edge(&mut x.1);
        }

        fn graft(parent: &mut Self::Value, child: Self::Value) {
            T::graft(&mut parent.0, child.0);
            U::graft(&mut parent.1, child.1);
        }
    }
    impl<T: Op, U: Op, V: Op> Op for (T, U, V) {
        type Value = (T::Value, U::Value, V::Value);

        fn singleton() -> Self::Value {
            (T::singleton(), U::singleton(), V::singleton())
        }

        fn add_edge(x: &mut Self::Value) {
            T::add_edge(&mut x.0);
            U::add_edge(&mut x.1);
            V::add_edge(&mut x.2);
        }

        fn graft(parent: &mut Self::Value, child: Self::Value) {
            T::graft(&mut parent.0, child.0);
            U::graft(&mut parent.1, child.1);
            V::graft(&mut parent.2, child.2);
        }
    }
    pub enum EdgeCount {}
    impl Op for EdgeCount {
        type Value = usize;

        fn singleton() -> Self::Value {
            0
        }

        fn add_edge(x: &mut Self::Value) {
            *x += 1;
        }

        fn graft(parent: &mut Self::Value, child: Self::Value) {
            *parent += child + 1
        }
    }
    pub enum VertexCount {}
    impl Op for VertexCount {
        type Value = usize;

        fn singleton() -> Self::Value {
            1
        }

        fn add_edge(_x: &mut Self::Value) {}

        fn graft(parent: &mut Self::Value, child: Self::Value) {
            *parent += child
        }
    }
    pub enum HasCycle {}
    impl Op for HasCycle {
        type Value = bool;

        fn singleton() -> Self::Value {
            false
        }

        fn add_edge(x: &mut Self::Value) {
            *x = true
        }

        fn graft(parent: &mut Self::Value, child: Self::Value) {
            *parent |= child
        }
    }
    #[derive(Clone, Default, Hash, PartialEq)]
    pub struct UnionFind<O: Op = ()> {
        parent_or_size: Vec<isize>,
        values: Vec<O::Value>,
        __marker: PhantomData<fn(O) -> O>,
    }
    impl<O: Op> UnionFind<O> {
        pub fn new(n: usize) -> Self {
            Self::from_values(repeat_with(|| O::singleton()).take(n).collect())
        }

        pub fn from_values(values: Vec<O::Value>) -> Self {
            let n = values.len();
            assert!(n <= std::usize::MAX / 2);
            Self {
                parent_or_size: vec![-1; n],
                values,
                __marker: PhantomData,
            }
        }

        pub fn find_mut(&mut self, mut x: usize) -> usize {
            assert!(x < self.parent_or_size.len());
            let mut p = self.parent_or_size[x];
            while 0 <= p {
                if 0 <= self.parent_or_size[p as usize] {
                    self.parent_or_size[x] = self.parent_or_size[p as usize];
                }
                x = p as usize;
                p = self.parent_or_size[x];
            }
            x
        }

        pub fn find(&self, mut x: usize) -> usize {
            assert!(x < self.parent_or_size.len());
            let mut p = self.parent_or_size[x];
            while 0 <= p {
                x = p as usize;
                p = self.parent_or_size[x];
            }
            x
        }

        pub fn same(&self, x: usize, y: usize) -> bool {
            self.find(x) == self.find(y)
        }

        pub fn is_root(&self, x: usize) -> bool {
            x == self.find(x)
        }

        pub fn get_value(&self, x: usize) -> &O::Value {
            assert!(x < self.parent_or_size.len());
            &self.values[self.find(x)]
        }

        pub fn value_mut(&mut self, x: usize) -> &mut O::Value {
            assert!(x < self.parent_or_size.len());
            let x = self.find(x);
            &mut self.values[x]
        }

        pub fn value(&self, x: usize) -> O::Value
        where
            O::Value: Copy,
        {
            assert!(x < self.parent_or_size.len());
            self.values[self.find(x)]
        }

        pub fn union(&mut self, mut x: usize, mut y: usize) -> bool {
            assert!(x < self.parent_or_size.len());
            assert!(y < self.parent_or_size.len());
            x = self.find_mut(x);
            y = self.find_mut(y);
            if x == y {
                O::add_edge(&mut self.values[x]);
                false
            } else {
                if self.parent_or_size[x] < self.parent_or_size[y] {
                    swap(&mut x, &mut y);
                }
                let aug = take(&mut self.values[x]);
                O::graft(&mut self.values[y], aug);
                self.parent_or_size[y] += replace(&mut self.parent_or_size[x], y as isize);
                true
            }
        }
    }
    impl<O: Op> Debug for UnionFind<O>
    where
        O::Value: Debug,
    {
        fn fmt(&self, f: &mut Formatter<'_>) -> Result {
            let n = self.parent_or_size.len();
            let mut groups = vec![Vec::new(); n];
            for i in 0..n {
                groups[self.find(i)].push(i);
            }
            f.debug_list()
                .entries(
                    groups
                        .into_iter()
                        .filter(|group| !group.is_empty())
                        .map(|list| (&self.values[self.find(*list.first().unwrap())], list)),
                )
                .finish()
        }
    }
}
// }}}

yukicoder

結果

テストケース

ソースコード