結果

問題 No.3425 Mod K Graph Increments (Easy)
コンテスト
ユーザー elphe
提出日時 2026-01-11 15:26:43
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 1,365 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,025 ms
コンパイル使用メモリ 412,468 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 15:27:11
合計ジャッジ時間 26,383 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

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>>, b: &mut Vec<u32>, k: u32) {
        if next_of[cur_pos as usize].len() == 1 && next_of[cur_pos as usize][0] == from {
            return;
        }
        for &next in next_of[cur_pos as usize].iter().filter(|&x| *x != from) {
            rec(next, cur_pos, next_of, 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);
    rec(0, 0, &next_of, &mut b, k);
    b[0] == 0
}

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