結果

問題 No.3694 犬猿の仲
コンテスト
ユーザー norioc
提出日時 2026-09-22 06:06:24
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 93 ms / 2,000 ms
+ 503µs
コード長 1,439 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,682 ms
コンパイル使用メモリ 203,680 KB
実行使用メモリ 37,000 KB
最終ジャッジ日時 2026-09-22 06:06:28
合計ジャッジ時間 3,264 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(non_snake_case, unused_imports)]

use std::collections::{BinaryHeap, HashMap, HashSet};
use proconio::{input, marker::Usize1, marker::Chars};
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! d {
    ( $( $x:expr ),* $(,)? ) => {
        eprintln!(
            concat!( $( stringify!($x), "={:?} " ),* ),
            $( $x ),*
        );
    };
}

#[allow(dead_code)]
fn yn(b: bool) -> &'static str {
    if b { "Yes" } else { "No" }
}



fn dfs(v: usize, adj: &HashMap<usize, Vec<usize>>, nodes: &mut Vec<i64>) -> bool {
    let mut res = true;

    if let Some(vs) = adj.get(&v) {
        for &to in vs.iter() {
            if to == v { continue }

            if nodes[to] == -1 {
                nodes[to] = nodes[v] ^ 1;
                res &= dfs(to, adj, nodes);
            } else if nodes[to] == nodes[v] {
                return false;
            }
        }
    }

    res
}

fn main() {
    input! {
        N: usize,
        M: usize,
    }

    let mut adj = HashMap::<usize, Vec<usize>>::new();
    for _ in 0..M {
        input! {
            a: Usize1,
            b: Usize1,
        }

        adj.entry(a).or_default().push(b);
        adj.entry(b).or_default().push(a);
    }

    let mut ans = true;
    let mut nodes = vec![-1; N];
    for i in 0..N {
        if nodes[i] != -1 { continue }

        nodes[i] = 0;
        ans &= dfs(i, &adj, &mut nodes);
    }

    println!("{}", yn(ans));
}
0