結果
問題 | No.1078 I love Matrix Construction |
ユーザー | Strorkis |
提出日時 | 2020-06-13 14:05:51 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 226 ms / 2,000 ms |
コード長 | 4,065 bytes |
コンパイル時間 | 2,448 ms |
コンパイル使用メモリ | 148,828 KB |
実行使用メモリ | 60,368 KB |
最終ジャッジ日時 | 2023-09-07 08:44:02 |
合計ジャッジ時間 | 6,515 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 0 ms
4,380 KB |
testcase_02 | AC | 21 ms
10,400 KB |
testcase_03 | AC | 60 ms
23,980 KB |
testcase_04 | AC | 95 ms
32,604 KB |
testcase_05 | AC | 101 ms
27,320 KB |
testcase_06 | AC | 19 ms
10,136 KB |
testcase_07 | AC | 7 ms
5,036 KB |
testcase_08 | AC | 87 ms
27,772 KB |
testcase_09 | AC | 4 ms
4,376 KB |
testcase_10 | AC | 226 ms
60,368 KB |
testcase_11 | AC | 97 ms
34,320 KB |
testcase_12 | AC | 166 ms
49,664 KB |
testcase_13 | AC | 224 ms
55,932 KB |
testcase_14 | AC | 134 ms
39,360 KB |
testcase_15 | AC | 201 ms
53,072 KB |
testcase_16 | AC | 5 ms
4,380 KB |
testcase_17 | AC | 1 ms
4,380 KB |
testcase_18 | AC | 14 ms
8,016 KB |
testcase_19 | AC | 35 ms
16,208 KB |
testcase_20 | AC | 30 ms
15,892 KB |
testcase_21 | AC | 2 ms
4,376 KB |
ソースコード
struct SCC { n: usize, graph: Vec<Vec<usize>>, rev_graph: Vec<Vec<usize>>, post_order: Vec<usize>, component: Vec<usize>, } impl SCC { fn new(n: usize) -> SCC { SCC { n, graph: vec![Vec::new(); n], rev_graph: vec![Vec::new(); n], component: vec![n; n], post_order: Vec::with_capacity(n), } } fn add_edge(&mut self, from: usize, to: usize) { self.graph[from].push(to); self.rev_graph[to].push(from); } fn dfs(&mut self, from: usize) { self.component[from] = self.n + 1; for to in self.graph[from].to_owned() { if self.component[to] == self.n { self.dfs(to); } } self.post_order.push(from); } fn rev_dfs(&mut self, from: usize, k: usize) { self.component[from] = k; for to in self.rev_graph[from].to_owned() { if self.component[to] > self.n { self.rev_dfs(to, k); } } } fn solve(&mut self) { for i in 0..self.n { if self.component[i] == self.n { self.dfs(i); } } let mut k: usize = 0; for i in (0..self.n).rev() { if self.component[self.post_order[i]] > self.n { self.rev_dfs(self.post_order[i], k); k += 1; } } } } struct TwoSAT { n: usize, scc: SCC, } impl TwoSAT { fn new(n: usize) -> TwoSAT { TwoSAT { n, scc: SCC::new(n * 2), } } fn add_closure(&mut self, x: usize, y: usize) { self.scc.add_edge((x + self.n) % (self.n * 2), y); self.scc.add_edge((y + self.n) % (self.n * 2), x); } fn solve(&mut self) -> Option<Vec<bool>> { self.scc.solve(); let mut res = vec![false; self.n]; for i in 0..self.n { if self.scc.component[i] == self.scc.component[i + self.n] { return None; } res[i] = self.scc.component[i] > self.scc.component[i + self.n]; } Some(res) } } use std::io::{BufRead, Write}; fn main() { let stdin = std::io::stdin(); let stdout = std::io::stdout(); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); let n: usize = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); buf.trim_end().parse().unwrap() }; let s: Vec<usize> = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse::<usize>().unwrap() - 1).collect() }; let t: Vec<usize> = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse::<usize>().unwrap() - 1).collect() }; let u: Vec<usize> = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse().unwrap()).collect() }; let m = n * n; let mut two_sat = TwoSAT::new(m); for i in 0..n { for j in 0..n { match u[i] { 0 => two_sat.add_closure(s[i] * n + j, j * n + t[i]), 1 => two_sat.add_closure(s[i] * n + j + m, j * n + t[i]), 2 => two_sat.add_closure(s[i] * n + j, j * n + t[i] + m), _ => two_sat.add_closure(s[i] * n + j + m, j * n + t[i] + m), } } } let ans = two_sat.solve(); let ans = match ans { Some(res) => res, None => { writeln!(writer, "-1").unwrap(); return; } }; for (i, &value) in ans.iter().enumerate() { write!(writer, "{}", if value { 1 } else { 0 }).unwrap(); write!(writer, "{}", if i % n < n - 1 { ' ' } else { '\n' }).unwrap(); } }