結果
問題 |
No.2780 The Bottle Imp
|
ユーザー |
|
提出日時 | 2024-06-12 06:33:17 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 2,268 bytes |
コンパイル時間 | 16,506 ms |
コンパイル使用メモリ | 378,540 KB |
実行使用メモリ | 33,280 KB |
最終ジャッジ日時 | 2024-06-12 06:33:38 |
合計ジャッジ時間 | 18,364 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
use proconio::input; fn main() { input!{ n: usize, } // 有向辺と逆辺 let mut uv = vec![Vec::new(); n]; let mut ruv = vec![Vec::new(); n]; for from in 1..=n { input!{ m: usize, } if m == 0 { continue; } input!{ a: [usize; m], } for to in a { uv[from-1].push(to-1); ruv[to-1].push(from-1); } } // -- 強連結成分分解 -- // 有向辺DFSして帰りがけに頂点を記録 fn dfs(spos: usize, uv: &Vec<Vec<usize>>, n: usize, used: &mut Vec<bool>, orders: &mut Vec<usize>){ used[spos] = true; for &npos in &uv[spos] { if used[npos] { continue; } dfs(npos, uv, n, used, orders); } orders.push(spos); } let mut used = vec![false; n]; let mut orders = Vec::new(); for i in 0..n { if used[i] { continue; } dfs(i, &uv, n, &mut used, &mut orders); } // 記録した頂点と逆順に逆辺有向辺DFS fn rdfs(spos: usize, ruv: &Vec<Vec<usize>>, n: usize, used: &mut Vec<bool>, compo: &mut Vec<Vec<usize>>, cnt: usize) { used[spos] = true; compo[cnt].push(spos); for &npos in &ruv[spos] { if used[npos] { continue; } rdfs(npos, ruv, n, used, compo, cnt); } } let mut compo_cnt = 0; let mut used = vec![false; n]; let mut compo = Vec::new(); orders.reverse(); for &i in &orders { if used[i] { continue; } compo.push(Vec::new()); rdfs(i, &ruv, n, &mut used, &mut compo, compo_cnt); compo_cnt += 1; } // -- 強連結成分分解 -- // 各頂点を連結成分のグループに割り当て let mut compo_group = vec![0; n]; for i in 0..compo.len() { for &c in &compo[i] { compo_group[c] = i; } } // 初めの連結成分が0でない場合は、No if compo_group[0] != 0 { println!("No"); return; } // 連結成分を順番に辿る // 辿ることができない連結成分があったらNo for i in 0..compo.len()-1 { let mut f = false; // 各連結成分の頂点 for &from in &compo[i] { // 各連結成分にある有向辺 for &to in &uv[from] { // k->l について、連結成分が連番であればよい。 if compo_group[from] + 1 == compo_group[to] { f = true; } } } if !f { println!("No"); return; } } println!("Yes"); }