結果

問題 No.3695 同室と別室
コンテスト
ユーザー urectanc
提出日時 2026-09-09 23:11:41
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 45 ms / 2,000 ms
+ 783µs
コード長 1,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,294 ms
コンパイル使用メモリ 191,380 KB
実行使用メモリ 35,872 KB
最終ジャッジ日時 2026-09-09 23:11:58
合計ジャッジ時間 12,741 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use ac_library::{Dsu, ModInt998244353};
use proconio::{input, marker::Usize1};

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize, q: usize,
        queries: [(u8, Usize1, Usize1); q],
    }

    let mut dsu = Dsu::new(n);
    let mut graph = vec![vec![]; n];
    for &(t, a, b) in &queries {
        if !dsu.same(a, b) {
            dsu.merge(a, b);
            graph[a].push((b, t));
            graph[b].push((a, t));
        }
    }

    let mut color = vec![2u8; n];
    let mut stack = vec![];
    for root in 0..n {
        if color[root] != 2 {
            continue;
        }
        color[root] = 0;
        stack.push((root, !0));

        while let Some((v, p)) = stack.pop() {
            for &(u, w) in &graph[v] {
                if u == p {
                    continue;
                }
                color[u] = color[v] ^ w;
                stack.push((u, v));
            }
        }
    }

    for &(t, a, b) in &queries {
        if color[a] != color[b] ^ t {
            println!("0");
            return;
        }
    }

    let k = dsu.groups().len();
    let ans = Mint::raw(2).pow(k as _);
    println!("{ans}");
}
0