結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-16 02:18:54 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 1,318 bytes |
コンパイル時間 | 14,740 ms |
コンパイル使用メモリ | 392,392 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 23:26:37 |
合計ジャッジ時間 | 18,841 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
use std::io::*;fn mul(a: &Vec<Vec<bool>>, b: &Vec<Vec<bool>>) -> Vec<Vec<bool>> {let n = a.len();let m = b[0].len();let mut c = vec![vec![false; m]; n];for k in 0..n {for i in 0..n {for j in 0..m {c[i][j] |= a[i][k] & b[k][j];}}}c}fn main() {let mut s: String = String::new();std::io::stdin().read_to_string(&mut s).ok();let mut itr = s.trim().split_whitespace();let n: usize = itr.next().unwrap().parse().unwrap();let m: usize = itr.next().unwrap().parse().unwrap();let mut t: usize = itr.next().unwrap().parse().unwrap();let mut a = vec![vec![false; n]; n];let mut res = vec![vec![false; n]; n];for _ in 0..m {let u: usize = itr.next().unwrap().parse().unwrap();let v: usize = itr.next().unwrap().parse().unwrap();a[v][u] = true;}for i in 0..n {res[i][i] = true;}while t > 0 {if t & 1 == 1 {res = mul(&res, &a);}a = mul(&a, &a);t >>= 1;}let mut from = vec![vec![false; 1]; n];from[0][0] = true;let to = mul(&res, &from);let mut ans = 0;for i in 0..n {if to[i][0] {ans += 1;}}println!("{}", ans);}