結果
問題 |
No.30 たこやき工場
|
ユーザー |
|
提出日時 | 2022-09-06 13:41:31 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,624 bytes |
コンパイル時間 | 15,702 ms |
コンパイル使用メモリ | 377,692 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-21 15:01:10 |
合計ジャッジ時間 | 13,708 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
コンパイルメッセージ
warning: unused import: `VecDeque` --> src/main.rs:1:24 | 1 | use std::collections::{VecDeque, BinaryHeap}; | ^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default
ソースコード
use std::collections::{VecDeque, BinaryHeap}; fn topologycal_sort(paths: &Vec<Vec<(usize, usize)>>) -> Vec<usize> { let n = paths.len(); let mut ret = vec![]; let mut ins = vec![0usize; n]; for i in 0..n { for &(v, _) in paths[i].iter() { ins[v] += 1; } } let mut que = BinaryHeap::new(); for i in 0..n { if ins[i] == 0 { que.push(i); } } while let Some(x) = que.pop() { ret.push(x); for &(v, _) in paths[x].iter() { ins[v] -= 1; if ins[v] == 0 { que.push(v); } } } ret } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut m = String::new(); std::io::stdin().read_line(&mut m).ok(); let m: usize = m.trim().parse().unwrap(); let mut paths = vec![vec![]; n]; for _ in 0..m { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let p = temp[0]-1; let q = temp[1]; let r = temp[2]-1; paths[r].push((p, q)); } let orders = topologycal_sort(&paths); let mut dp = vec![0usize; n]; dp[n-1] = 1; for &u in orders.iter() { for &(v, cnt) in paths[u].iter() { dp[v] += dp[u] * cnt; } if paths[u].len() > 0 { dp[u] = 0; } } for &v in dp.iter().take(n-1) { println!("{}", v); } }