結果
| 問題 |
No.2674 k-Walk on Bipartite
|
| コンテスト | |
| ユーザー |
 ngtkana
|
| 提出日時 | 2024-03-02 00:00:47 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 132 ms / 2,000 ms |
| コード長 | 11,142 bytes |
| コンパイル時間 | 12,503 ms |
| コンパイル使用メモリ | 391,176 KB |
| 実行使用メモリ | 18,788 KB |
| 最終ジャッジ日時 | 2024-09-29 22:57:48 |
| 合計ジャッジ時間 | 15,325 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
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()
}
}
}
// }}}