結果

問題 No.2733 Just K-times TSP
ユーザー maguroflymagurofly
提出日時 2024-04-19 22:19:45
言語 Rust
(1.77.0)
結果
AC  
実行時間 174 ms / 2,000 ms
コード長 1,798 bytes
コンパイル時間 6,180 ms
コンパイル使用メモリ 147,328 KB
実行使用メモリ 47,488 KB
最終ジャッジ日時 2024-04-19 22:19:53
合計ジャッジ時間 5,897 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 0 ms
5,376 KB
testcase_03 AC 0 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 0 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 0 ms
5,376 KB
testcase_09 AC 0 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 11 ms
5,888 KB
testcase_18 AC 13 ms
6,016 KB
testcase_19 AC 15 ms
6,016 KB
testcase_20 AC 4 ms
5,376 KB
testcase_21 AC 9 ms
5,888 KB
testcase_22 AC 114 ms
47,488 KB
testcase_23 AC 12 ms
5,888 KB
testcase_24 AC 74 ms
24,448 KB
testcase_25 AC 69 ms
24,448 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 6 ms
5,376 KB
testcase_30 AC 15 ms
5,888 KB
testcase_31 AC 37 ms
12,032 KB
testcase_32 AC 87 ms
24,448 KB
testcase_33 AC 174 ms
47,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]

fn main() {
	let [N, M, K] = read_words::<usize>()[..] else { return };
	let edges = (0 .. M).map(|_| read_words::<usize>() ).collect::<Vec<_>>();
	let mut graph = vec![vec![]; N];
	for edge in &edges {
		let u = edge[0] - 1;
		let v = edge[1] - 1;
		graph[u].push(v);
		graph[v].push(u);
	}
	let mut pow = vec![1; N + 1];
	for i in 0 .. N {
		pow[i + 1] = pow[i] * (K + 1) % MOD;
	}
	let mut dp = vec![vec![0; N]; pow[N]];
	for i in 0 .. N {
		dp[pow[i]][i] = 1;
	}
	for state in 1 .. pow[N] {
		for last in 0 .. N {
			let c = dp[state][last];
			for &v in &graph[last] {
				let count = state / pow[v] % (K + 1);
				if count < K {
					let x = &mut dp[state + pow[v]][v];
					*x = add(*x, c);
				}
			}
		}
	}
	
	let mut sum = 0;
	for i in 0 .. N {
	    sum += dp[pow[N] - 1][i];
	    sum %= MOD;
	}
	println!("{}", sum);
}

fn add(x: usize, y: usize) -> usize {
	let mut z = x + y;
	if z >= MOD {
		z -= MOD;
	}
	z
}

type Int = usize;
const MOD: Int = 998_244_353;
const INF: Int = 1_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];

use std::collections::*;
use std::cmp::Reverse;

fn read_line() -> String { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).ok(); buf }
fn read_words<T: std::str::FromStr>() -> Vec<T> where T::Err: std::fmt::Debug { read_line().split_whitespace().map(|x| T::from_str(x).unwrap() ).collect() }

fn yes() { println!("{}", YESNO[0]); }
fn no() { println!("{}", YESNO[1]); }
fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }
fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }
0