結果
| 問題 | No.1078 I love Matrix Construction |
| ユーザー |
 akakimidori
|
| 提出日時 | 2020-06-12 21:48:02 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 143 ms / 2,000 ms |
| コード長 | 6,204 bytes |
| コンパイル時間 | 14,733 ms |
| コンパイル使用メモリ | 406,260 KB |
| 実行使用メモリ | 38,688 KB |
| 最終ジャッジ日時 | 2024-06-24 04:48:05 |
| 合計ジャッジ時間 | 19,872 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
// ---------- 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();}