結果

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

ソースコード

diff #
raw source code 

//use std::collections::VecDeque;
use proconio::{input, marker::Usize1};
const INF: usize = 1 << 60;
fn main() {
    input! {
		t: usize,
	}
	for _ in 0..t {
		solve();
	}
}

fn solve() {
	input! {
		n: usize, // 頂点数
		m: usize, // 辺の数
		k: usize, // mod
		uv: [(Usize1, Usize1); m],
		b: [usize; n],
	}

	// グラフ(木)の構築
	let tree = make_graph(n, m, &uv);

	// 木の葉から貪欲に。最後の頂点が一致すればOK
	let mut isok = false;
	dfs(n, m, &tree, 0, INF, &b, &mut isok, k);

	println!("{}", if isok {"Yes"} else {"No"});
}

fn make_graph(n: usize, _m: usize, uv: &Vec<(usize, usize)>) -> Vec<Vec<usize>>{
	let mut ret = vec![Vec::new(); n];
	for &(u, v) in uv {
		ret[u].push(v);
		ret[v].push(u);
	}
	ret
}

fn dfs(n: usize, _m:usize, tree: &Vec<Vec<usize>>, cpos: usize, ppos: usize, b: &Vec<usize>, 
	isok: &mut bool, k: usize,
) -> usize{
	// 操作済みの操作回数
	let mut cnt = 0;

	// 自身の子を調べる
	for &npos in &tree[cpos] {
		// あと戻り禁止
		if npos == ppos { continue; }

		// 操作回数を取得
		cnt += dfs(n, _m, tree, npos, cpos, b, isok, k);
		cnt %= k;
	}

// {
// 	println!("cpos{}:{} b{}", cpos, cnt, b[cpos]);
// }

	// 必要回数を取得
	let ret = (b[cpos] + k - cnt) % k;

	// 根なら判定する
	if cpos == 0 {
		if ret == 0 { *isok = true;}
	}
	ret
}


/*
1
7 6 5
1 2
2 3
3 4
2 5
5 6
5 7
1 3 1 4 2 1 1

3 3 1 4 2 1 1

*/
0