結果

問題 No.2733 Just K-times TSP
ユーザー magurofly
提出日時 2024-04-19 22:19:45
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 190 ms / 2,000 ms
コード長 1,798 bytes
コンパイル時間 13,537 ms
コンパイル使用メモリ 379,512 KB
実行使用メモリ 47,488 KB
最終ジャッジ日時 2024-10-11 15:46:24
合計ジャッジ時間 15,474 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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); } }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0