結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー elphe
提出日時 2026-01-11 16:24:29
言語 Rust
(1.92.0 + proconio + num)
結果
WA  
実行時間 -
コード長 1,579 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 26,410 ms
コンパイル使用メモリ 412,028 KB
実行使用メモリ 17,172 KB
最終ジャッジ日時 2026-01-11 16:24:57
合計ジャッジ時間 26,305 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        t: usize,
    }
    for _ in 0..t {
        input! {
            n: usize,
            m: usize,
            k: u32,
            edges: [(u32, u32); m],
            b: [u32; n],
        }

        println!("{}", output(solve(n, m, k, edges, b)));
    }
}

fn prepare(n: usize, edges: Vec<(u32, u32)>) -> Vec<Vec<u32>> {
    let mut next_of = vec![Vec::with_capacity(100); n];
    for (u, v) in edges {
        next_of[(u - 1) as usize].push(v - 1);
        next_of[(v - 1) as usize].push(u - 1);
    }
    next_of
}

fn solve(n: usize, m: usize, k: u32, edges: Vec<(u32, u32)>, mut b: Vec<u32>) -> bool {
    fn rec(
        cur_pos: u32,
        from: u32,
        next_of: &Vec<Vec<u32>>,
        is_reached: &mut Vec<bool>,
        b: &mut Vec<u32>,
        k: u32,
    ) {
        is_reached[cur_pos as usize] = true;
        for &next in next_of[cur_pos as usize].iter().filter(|&x| *x != from) {
            if !is_reached[next as usize] {
                rec(next, cur_pos, next_of, is_reached, b, k);
                b[cur_pos as usize] = (k + b[cur_pos as usize] - b[next as usize]) % k;
                b[next as usize] = 0;
            }
        }
    }

    let next_of = prepare(n, edges);
    let mut is_reached = vec![false; n];
    rec(0, 0, &next_of, &mut is_reached, &mut b, k);
    if n == m + 1 {
        b[0] == 0
    } else {
        k & 2 == 1 || b[0] & 2 == 0
    }
}

fn output(ans: bool) -> &'static str {
    match ans {
        true => "Yes",
        false => "No",
    }
}
0