結果
問題 | No.483 マッチ並べ |
ユーザー | nebocco |
提出日時 | 2021-03-08 20:49:56 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 15,939 bytes |
コンパイル時間 | 17,773 ms |
コンパイル使用メモリ | 383,684 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-10 11:34:55 |
合計ジャッジ時間 | 15,444 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | AC | 1 ms
6,820 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 1 ms
6,816 KB |
testcase_07 | AC | 1 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,820 KB |
testcase_09 | AC | 1 ms
6,820 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 1 ms
6,816 KB |
testcase_12 | AC | 1 ms
6,816 KB |
testcase_13 | AC | 1 ms
6,816 KB |
testcase_14 | AC | 1 ms
6,816 KB |
testcase_15 | AC | 1 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,816 KB |
testcase_17 | AC | 1 ms
6,820 KB |
testcase_18 | AC | 1 ms
6,816 KB |
testcase_19 | AC | 1 ms
6,816 KB |
testcase_20 | AC | 1 ms
6,816 KB |
testcase_21 | AC | 1 ms
6,816 KB |
testcase_22 | AC | 1 ms
6,816 KB |
testcase_23 | AC | 1 ms
6,816 KB |
testcase_24 | AC | 1 ms
6,816 KB |
testcase_25 | AC | 1 ms
6,816 KB |
testcase_26 | AC | 1 ms
6,816 KB |
testcase_27 | AC | 1 ms
6,816 KB |
testcase_28 | AC | 1 ms
6,816 KB |
testcase_29 | AC | 1 ms
6,820 KB |
testcase_30 | AC | 1 ms
6,816 KB |
testcase_31 | AC | 1 ms
6,820 KB |
testcase_32 | AC | 1 ms
6,816 KB |
testcase_33 | AC | 1 ms
6,820 KB |
testcase_34 | AC | 1 ms
6,820 KB |
testcase_35 | AC | 1 ms
6,816 KB |
testcase_36 | AC | 1 ms
6,816 KB |
testcase_37 | AC | 1 ms
6,816 KB |
testcase_38 | AC | 1 ms
6,816 KB |
testcase_39 | AC | 1 ms
6,816 KB |
testcase_40 | AC | 1 ms
6,816 KB |
testcase_41 | AC | 2 ms
6,820 KB |
testcase_42 | AC | 1 ms
6,816 KB |
testcase_43 | AC | 1 ms
6,820 KB |
testcase_44 | AC | 2 ms
6,816 KB |
testcase_45 | AC | 1 ms
6,816 KB |
testcase_46 | AC | 1 ms
6,816 KB |
testcase_47 | AC | 1 ms
6,820 KB |
testcase_48 | AC | 1 ms
6,820 KB |
testcase_49 | AC | 1 ms
6,820 KB |
testcase_50 | AC | 1 ms
6,820 KB |
testcase_51 | AC | 1 ms
6,820 KB |
testcase_52 | AC | 1 ms
6,820 KB |
testcase_53 | AC | 1 ms
6,816 KB |
testcase_54 | AC | 1 ms
6,816 KB |
testcase_55 | AC | 1 ms
6,820 KB |
ソースコード
fn main() { let mut io = IO::new(); input!{ from io, n: usize, l: [(Usize1, Usize1, Usize1, Usize1); n] } let m = 100; let mut sat = TwoSat::new(n); let mut g = vec![Vec::new(); m*m]; for (i, &(a, b, c, d)) in l.iter().enumerate() { let u = a * m + b; let v = c * m + d; for &(j, x) in &g[u] { sat.add_clause(i, false, j, x); } for &(j, x) in &g[v] { sat.add_clause(i, true, j, x); } g[u].push((i, false)); g[v].push((i, true)); } let ans = if sat.solve().is_some() { "YES" } else { "NO" }; io.println(ans); } // * verified: https://judge.yosupo.jp/submission/26465 // ------------ 2-SAT start ------------ // * verified: https://judge.yosupo.jp/submission/26463 // ------------ Strongly Connected Components start ------------ // ! DirectedGraph::reverse() is too heavy pub trait SCC { fn strongly_connected(&self) -> (usize, Vec<usize>); fn groups(&self) -> Vec<Vec<usize>>; } impl<C: Cost> SCC for DirectedGraph<C> { fn strongly_connected(&self) -> (usize, Vec<usize>) { fn _scc_dfs<C: Cost>(graph: &DirectedGraph<C>, x: usize, res: &mut [Option<usize>]) { for y in graph.edges_from(x) { if res[y.to].is_none() { res[y.to] = res[x]; _scc_dfs(graph, y.to, res); } } } let n = self.size(); let post_backward = Traversal::post_order(&self.backward); let mut res: Vec<Option<usize>> = vec![None; n]; let mut cnt = 0; for &x in post_backward.index.iter().rev() { if res[x].is_none() { res[x] = Some(cnt); _scc_dfs(self, x, &mut res); cnt += 1; } } ( cnt, res.iter().map(|x| cnt - 1 - x.unwrap()).collect(), ) } fn groups(&self) -> Vec<Vec<usize>> { let (c, g) = self.strongly_connected(); let mut res = vec![Vec::new(); c]; for (i, &x) in g.iter().enumerate() { res[x].push(i); } res } } // ------------ Strongly Connected Components end ------------ pub struct TwoSat(DirectedGraph<Void>); impl TwoSat { pub fn new(n: usize) -> Self { Self(DirectedGraph::new(2 * n)) } pub fn add_clause(&mut self, i: usize, f: bool, j: usize, g: bool) { self.0.add_edge(2 * i + !f as usize, 2 * j + g as usize, Void()); self.0.add_edge(2 * j + !g as usize, 2 * i + f as usize, Void()); } pub fn solve(&self) -> Option<Vec<bool>> { self.0 .strongly_connected().1 .chunks_exact(2) .map(|v| { use std::cmp::Ordering::*; match v[0].cmp(&v[1]) { Equal => None, Less => Some(true), Greater => Some(false), } }) .collect() } } // ------------ 2-SAT end ------------ #[derive(Debug, Clone)] pub struct Traversal { pub index: Vec<usize>, pub time: Vec<usize>, } impl Traversal { pub fn pre_order<C: Cost>(graph: &[Vec<Edge<C>>]) -> Self { fn _dfs<C: Cost>(graph: &[Vec<Edge<C>>], x: usize, res: &mut PermutationBuilder) { res.visit(x); for &y in graph[x].iter() { if !res.on_stack(y.to) { _dfs(graph, y.to, res); } } } let n = graph.len(); let mut res = PermutationBuilder::new(n); for i in 0..n { if !res.on_stack(i) { _dfs(graph, i, &mut res); } } res.build() } pub fn post_order<C: Cost>(graph: &[Vec<Edge<C>>]) -> Self { fn _dfs<C: Cost>(graph: &[Vec<Edge<C>>], x: usize, ckd: &mut [bool], res: &mut PermutationBuilder) { for &y in graph[x].iter() { if !std::mem::replace(&mut ckd[y.to], true) { _dfs(graph, y.to, ckd, res); } } res.visit(x); } let n = graph.len(); let mut ckd = vec![false; n]; let mut res = PermutationBuilder::new(n); for i in 0..n { if !std::mem::replace(&mut ckd[i], true) { _dfs(graph, i, &mut ckd, &mut res); } } res.build() } } #[derive(Debug, Clone)] struct PermutationBuilder { index: Vec<usize>, time: Vec<usize>, } impl PermutationBuilder { fn new(n: usize) -> Self { Self { index: Vec::with_capacity(n), time: vec![n; n], } } fn build(self) -> Traversal { Traversal { index: self.index, time: self.time, } } #[allow(dead_code)] fn is_empty(&self) -> bool { self.time.is_empty() } fn len(&self) -> usize { self.time.len() } fn time(&self) -> usize { self.index.len() } fn visit(&mut self, x: usize) { assert!(!self.on_stack(x)); self.time[x] = self.time(); self.index.push(x); } fn on_stack(&self, x: usize) -> bool { self.time[x] != self.len() } } // ------------ Graph impl start ------------ pub trait Cost: Element + Clone + Copy + std::fmt::Display + Eq + Ord + Zero + One + Add<Output = Self> + AddAssign + Sub<Output = Self> + Neg<Output = Self> { const MAX: Self; } #[derive(Copy, Clone)] pub struct Edge<C = Void> { // pub from: usize, pub to: usize, pub cost: C, pub id: usize } pub struct UndirectedGraph<C>(pub Vec<Vec<Edge<C>>>, pub usize); pub struct DirectedGraph<C>{ pub forward: Vec<Vec<Edge<C>>>, pub backward: Vec<Vec<Edge<C>>>, pub count: usize, } pub trait Graph<C: Element> { fn new(size: usize) -> Self; fn size(&self) -> usize; fn add_edge(&mut self, u: usize, v: usize, cost: C); fn edges_from(&self, v: usize) -> std::slice::Iter<Edge<C>>; } impl<C: Element> Graph<C> for UndirectedGraph<C> { fn new(size: usize) -> Self { Self(vec![Vec::<Edge<C>>::new(); size], 0) } fn size(&self) -> usize { self.0.len() } fn add_edge(&mut self, u: usize, v: usize, cost: C) { self.0[u].push(Edge{ to: v, cost: cost.clone(), id: self.1 }); self.0[v].push(Edge{ to: u, cost: cost.clone(), id: self.1 }); self.1 += 1; } fn edges_from(&self, v: usize) -> std::slice::Iter<Edge<C>> { self.0[v].iter() } } impl<C: Element> Graph<C> for DirectedGraph<C> { fn new(size: usize) -> Self { Self { forward: vec![Vec::<Edge<C>>::new(); size], backward: vec![Vec::<Edge<C>>::new(); size], count: 0 } } fn size(&self) -> usize { self.forward.len() } fn add_edge(&mut self, u: usize, v: usize, cost: C) { self.forward[u].push(Edge{ to: v, cost: cost.clone(), id: self.count }); self.backward[v].push(Edge{ to: u, cost: cost.clone(), id: self.count }); self.count += 1; } fn edges_from(&self, v: usize) -> std::slice::Iter<Edge<C>> { self.forward[v].iter() } } impl<C: Element> DirectedGraph<C> { pub fn edges_to(&self, u: usize) -> std::slice::Iter<Edge<C>> { self.backward[u].iter() } pub fn reverse(&self) -> Self { Self { forward: self.backward.clone(), backward: self.forward.clone(), count: self.count, } } } macro_rules! impl_cost { ($($T:ident,)*) => { $( impl Cost for $T { const MAX: Self = std::$T::MAX; } )* }; } impl_cost! { i8, i16, i32, i64, i128, isize, } #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Void(); impl std::fmt::Display for Void { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "") } } impl Zero for Void { fn zero() -> Self { Void() } fn is_zero(&self) -> bool { true } } impl One for Void { fn one() -> Self { Void() } fn is_one(&self) -> bool { true } } impl Add for Void { type Output = Self; fn add(self, _: Self) -> Self { Void() } } impl AddAssign for Void { fn add_assign(&mut self, _: Self) {} } impl Sub for Void { type Output = Self; fn sub(self, _: Self) -> Self { Void() } } impl Neg for Void { type Output = Self; fn neg(self) -> Self { Void() } } impl Cost for Void { const MAX: Self = Void(); } // ------------ Graph impl end ------------ // ------------ algebraic traits start ------------ use std::marker::Sized; use std::ops::*; /// 元 pub trait Element: Sized + Clone + PartialEq {} impl<T: Sized + Clone + PartialEq> Element for T {} /// 結合性 pub trait Associative: Magma {} /// マグマ pub trait Magma: Element + Add<Output=Self> {} impl<T: Element + Add<Output=Self>> Magma for T {} /// 半群 pub trait SemiGroup: Magma + Associative {} impl<T: Magma + Associative> SemiGroup for T {} /// モノイド pub trait Monoid: SemiGroup + Zero {} impl<T: SemiGroup + Zero> Monoid for T {} pub trait ComMonoid: Monoid + AddAssign {} impl<T: Monoid + AddAssign> ComMonoid for T {} /// 群 pub trait Group: Monoid + Neg<Output=Self> {} impl<T: Monoid + Neg<Output=Self>> Group for T {} pub trait ComGroup: Group + ComMonoid {} impl<T: Group + ComMonoid> ComGroup for T {} /// 半環 pub trait SemiRing: ComMonoid + Mul<Output=Self> + One {} impl<T: ComMonoid + Mul<Output=Self> + One> SemiRing for T {} /// 環 pub trait Ring: ComGroup + SemiRing {} impl<T: ComGroup + SemiRing> Ring for T {} pub trait ComRing: Ring + MulAssign {} impl<T: Ring + MulAssign> ComRing for T {} /// 体 pub trait Field: ComRing + Div<Output=Self> + DivAssign {} impl<T: ComRing + Div<Output=Self> + DivAssign> Field for T {} /// 加法単元 pub trait Zero: Element { fn zero() -> Self; fn is_zero(&self) -> bool { *self == Self::zero() } } /// 乗法単元 pub trait One: Element { fn one() -> Self; fn is_one(&self) -> bool { *self == Self::one() } } macro_rules! impl_integer { ($($T:ty,)*) => { $( impl Associative for $T {} impl Zero for $T { fn zero() -> Self { 0 } fn is_zero(&self) -> bool { *self == 0 } } impl<'a> Zero for &'a $T { fn zero() -> Self { &0 } fn is_zero(&self) -> bool { *self == &0 } } impl One for $T { fn one() -> Self { 1 } fn is_one(&self) -> bool { *self == 1 } } impl<'a> One for &'a $T { fn one() -> Self { &1 } fn is_one(&self) -> bool { *self == &1 } } )* }; } impl_integer! { i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, } // ------------ algebraic traits end ------------ // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter<StdoutLock<'static>>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan<T: Scan>(&mut self) -> <T as Scan>::Output { <T as Scan>::scan(self) } pub fn scan_vec<T: Scan>(&mut self, n: usize) -> Vec<<T as Scan>::Output> { (0..n).map(|_| self.scan::<T>()).collect() } pub fn print<T: Print>(&mut self, x: T) { <T as Print>::print(self, x); } pub fn println<T: Print>(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln<T: Print, I: Iterator<Item = T>>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String, f32, f64); impl Scan for char { type Output = char; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().next().unwrap() } } pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec<char>; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::<usize>().wrapping_sub(1) } } impl<T: Scan, U: Scan> Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl<T: Scan, U: Scan, V: Scan> Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl<T: Scan, U: Scan, V: Scan, W: Scan> Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize, f32, f64); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl<T: Print, U: Print> Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl<T: Print, U: Print, V: Print> Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [[$kind:tt; $len1:expr]; $len2:expr] $($rest:tt)*) => { let $($mut)* $var = (0..$len2).map(|_| $io.scan_vec::<$kind>($len1)).collect::<Vec<Vec<$kind>>>(); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------