結果
問題 | No.1078 I love Matrix Construction |
ユーザー | akakimidori |
提出日時 | 2020-06-12 21:48:02 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 6,204 bytes |
コンパイル時間 | 1,270 ms |
コンパイル使用メモリ | 153,984 KB |
実行使用メモリ | 38,580 KB |
最終ジャッジ日時 | 2023-09-06 10:10:44 |
合計ジャッジ時間 | 4,876 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 11 ms
7,240 KB |
testcase_03 | AC | 27 ms
15,868 KB |
testcase_04 | AC | 35 ms
21,324 KB |
testcase_05 | AC | 38 ms
17,944 KB |
testcase_06 | AC | 10 ms
6,984 KB |
testcase_07 | AC | 4 ms
4,376 KB |
testcase_08 | AC | 33 ms
18,056 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 93 ms
38,580 KB |
testcase_11 | AC | 42 ms
22,300 KB |
testcase_12 | AC | 74 ms
33,584 KB |
testcase_13 | AC | 89 ms
36,352 KB |
testcase_14 | AC | 54 ms
25,452 KB |
testcase_15 | AC | 87 ms
34,352 KB |
testcase_16 | AC | 4 ms
4,376 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 8 ms
5,720 KB |
testcase_19 | AC | 16 ms
10,928 KB |
testcase_20 | AC | 16 ms
10,732 KB |
testcase_21 | AC | 2 ms
4,380 KB |
ソースコード
// ---------- begin Strongly Connected Components ---------- struct SCC { size: usize, edge: Vec<(usize, usize)>, id: Vec<usize>, } impl SCC { pub fn new(size: usize) -> Self { SCC { size: size, edge: vec![], id: Vec::with_capacity(size), } } pub fn add_edge(&mut self, from: usize, to: usize) { assert!(from < self.size && to < self.size); self.edge.push((from, to)); } fn build_graph<'a>(&self, buf: &'a mut [usize], cnt: &[usize], inv: bool) -> Vec<&'a mut [usize]> { let size = self.size; let mut index = vec![0; self.size]; for e in self.edge.iter() { let (f, t) = if inv { (e.1, e.0) } else { *e }; buf[self.edge.len() - cnt[f] + index[f]] = t; index[f] += 1; } let mut ans = Vec::with_capacity(size); let mut buf = Some(buf); for i in 0..size { let len = cnt[i] - cnt[i + 1]; let x = buf.take().unwrap(); let (x, y) = x.split_at_mut(len); ans.push(x); buf = Some(y); } ans } fn dfs1(&self, buf: &mut [usize], cnt: &[usize], q: &mut Vec<usize>) { let size = self.size; let graph = self.build_graph(buf, cnt, false); let mut visited = vec![false; size]; let mut stack = vec![]; for v in 0..size { if visited[v] { continue; } stack.clear(); visited[v] = true; stack.push((v, graph[v].iter())); while let Some((v, mut it)) = stack.pop() { let mut finish = true; while let Some(&u) = it.next() { if !visited[u] { visited[u] = true; finish = false; stack.push((v, it)); stack.push((u, graph[u].iter())); break; } } if finish { q.push(v); } } } } fn dfs2(&mut self, buf: &mut [usize], cnt: &[usize], q: &[usize]) { let size = self.size; let inv_graph = self.build_graph(buf, cnt, true); self.id.clear(); self.id.resize(size, size); let mut counter = 0; let mut stack = vec![]; for &v in q.iter().rev() { if self.id[v] < size { continue; } self.id[v] = counter; stack.clear(); stack.push(v); while let Some(v) = stack.pop() { self.id[v] = counter; for &u in inv_graph[v].iter() { if self.id[u] == size { self.id[u] = counter; stack.push(u); } } } counter += 1; } } pub fn build(&mut self) { let size = self.size; let mut cnt = vec![0; size + 1]; let mut inv_cnt = vec![0; size + 1]; for e in self.edge.iter() { cnt[e.0] += 1; inv_cnt[e.1] += 1; } for i in (0..size).rev() { cnt[i] += cnt[i + 1]; inv_cnt[i] += inv_cnt[i + 1]; } let mut buf = vec![0; self.edge.len()]; let mut q = Vec::with_capacity(size); self.dfs1(&mut buf, &cnt, &mut q); self.dfs2(&mut buf, &inv_cnt, &q); } pub fn get_array(&self) -> Vec<usize> { self.id.clone() } } // ---------- end Strongly Connected Components ---------- // ---------- begin 2-SAT ---------- struct SAT2 { size: usize, scc: SCC, } impl SAT2 { fn new(size: usize) -> Self { SAT2 { size: size, scc: SCC::new(2 * size), } } fn add(&mut self, a: usize, b: usize) { let size = self.size; let (x, ix) = if a >= size { (!a + size, !a) } else { (a, a + size) }; let (y, iy) = if b >= size { (!b + size, !b) } else { (b, b + size) }; self.scc.add_edge(ix, y); self.scc.add_edge(iy, x); } fn solve(&mut self) -> Option<Vec<bool>> { self.scc.build(); let id = self.scc.get_array(); let mut ans = vec![]; for i in 0..self.size { if id[i] == id[i + self.size] { return None; } else if id[i] < id[i + self.size] { ans.push(false); } else { ans.push(true); } } Some(ans) } } // ---------- end 2-SAT ---------- use std::io::Read; fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let s: Vec<usize> = (0..n).map(|_| { it.next().unwrap().parse::<usize>().unwrap() - 1 }).collect(); let t: Vec<usize> = (0..n).map(|_| { it.next().unwrap().parse::<usize>().unwrap() - 1 }).collect(); let u: Vec<usize> = it.map(|s| s.parse().unwrap()).collect(); let mut sat = SAT2::new(n * n); for i in 0..n { for j in 0..n { let x = s[i] * n + j; let y = j * n + t[i]; match u[i] { 0 => { sat.add(x, y); }, 1 => { sat.add(!x, y); }, 2 => { sat.add(x, !y) }, 3 => { sat.add(!x, !y); }, _ => unreachable!(), } } } if let Some(a) = sat.solve() { let mut out = String::new(); for i in 0..n { for j in 0..n { let a = a[i * n + j]; out.push_str(&format!("{} ", a as usize)); } out.pop(); out.push('\n'); } print!("{}", out); } else { println!("-1"); } } fn main() { run(); }