結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 2024-06-07 22:35:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 4,314 bytes |
コンパイル時間 | 18,149 ms |
コンパイル使用メモリ | 378,676 KB |
実行使用メモリ | 28,672 KB |
最終ジャッジ日時 | 2024-12-27 14:12:56 |
合計ジャッジ時間 | 21,227 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#![allow(non_snake_case, unused_imports)]use proconio::{fastout, input, marker::*};#[fastout]fn main() {input! {N: usize,}let mut edges = vec![];for i in 0..N {input! {M: usize,A: [Usize1; M],}for a in A {edges.push((i, a));}}let scc = strongly_connected_components(N, &edges);let (z, zi) = coordinate_compression(&scc);let n = z.len();let mut edges_set = std::collections::HashSet::new();let mut deg_out = vec![0; n];let mut deg_in = vec![0; N];for (u, v) in edges {if scc[u] == scc[v] {continue;}edges_set.insert((*zi.get(&scc[u]).unwrap(), *zi.get(&scc[v]).unwrap()));deg_out[*zi.get(&scc[u]).unwrap()] += 1;deg_in[*zi.get(&scc[v]).unwrap()] += 1;}let ord = topological_sort(n,&edges_set.iter().map(|&(u, v)| (u, v)).collect::<Vec<_>>(),);let s = *zi.get(&scc[0]).unwrap();if ord[s] != 0 {println!("No");return;}// eprintln!(// "scc: {}",// scc.iter()// .map(|x| x.to_string())// .collect::<Vec<_>>()// .join(" ")// );// eprintln!(// "ord: {}",// ord.iter()// .map(|x| x.to_string())// .collect::<Vec<_>>()// .join(" ")// );for i in 0..n - 1 {if deg_out[ord[i]] == 0 {println!("No");return;}let u = ord[i];let v = ord[i + 1];if !edges_set.contains(&(u, v)) {println!("No");return;}}for i in 1..n {if deg_in[ord[i]] == 0 {println!("No");return;}}println!("Yes");}fn coordinate_compression<T: std::cmp::Ord + Clone + Copy>(values: &[T],) -> (Vec<T>, std::collections::BTreeMap<T, usize>) {let s: std::collections::BTreeSet<T> = values.iter().cloned().collect();let z: Vec<T> = s.iter().cloned().collect();let zinv: std::collections::BTreeMap<T, usize> =z.iter().enumerate().map(|(i, &v)| (v, i)).collect();(z, zinv)}fn topological_sort(N: usize, E: &[(usize, usize)]) -> Vec<usize> {let mut graph = vec![vec![]; N];let mut out_degree = vec![0; N];let mut ord = vec![];for &(u, v) in E {graph[v].push(u);out_degree[u] += 1;}for i in 0..N {graph[i].sort();}let mut q = std::collections::VecDeque::new();for i in 0..N {if out_degree[i] == 0 {q.push_back(i);}}while let Some(now) = q.pop_front() {ord.push(now);for &nxt in graph[now].iter() {out_degree[nxt] -= 1;if out_degree[nxt] == 0 {q.push_back(nxt);}}}ord.reverse();return ord;}fn strongly_connected_components(N: usize, E: &Vec<(usize, usize)>) -> Vec<usize> {struct Graph {list: Vec<Vec<usize>>,seen: Vec<bool>,stop: Vec<usize>,}impl Graph {fn dfs(&mut self, now: usize) {self.seen[now] = true;for &nxt in self.list[now].clone().iter() {if self.seen[nxt] {continue;}self.dfs(nxt);}self.stop.push(now);}}let mut g = vec![vec![]; N];let mut g_inv = vec![vec![]; N];for &(u, v) in E.iter() {g[u].push(v);g_inv[v].push(u);}let mut G = Graph {list: g,seen: vec![false; N],stop: vec![],};for i in 0..N {if !G.seen[i] {G.dfs(i);}}let mut stop = G.stop;stop.reverse();let mut G_inv = Graph {list: g_inv,seen: vec![false; N],stop: vec![],};let mut ret = vec![0; N];let mut cnt = 0;for i in stop {if !G_inv.seen[i] {G_inv.dfs(i);for &v in G_inv.stop.iter() {ret[v] = cnt;}G_inv.stop = vec![];cnt += 1;}}return ret;}