結果
| 問題 | No.1400 すごろくで世界旅行 |
| ユーザー |
 koba-e964
|
| 提出日時 | 2021-12-29 01:33:59 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 3,138 ms / 3,153 ms |
| コード長 | 7,829 bytes |
| コンパイル時間 | 13,050 ms |
| コンパイル使用メモリ | 378,752 KB |
| 実行使用メモリ | 18,944 KB |
| 最終ジャッジ日時 | 2024-10-03 01:48:24 |
| 合計ジャッジ時間 | 18,071 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
ソースコード
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr,) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}/*** Union-Find tree.* Verified by https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9253305*/struct UnionFind { disj: Vec<usize>, rank: Vec<usize> }impl UnionFind {fn new(n: usize) -> Self {let disj = (0..n).collect();UnionFind { disj: disj, rank: vec![1; n] }}fn root(&mut self, x: usize) -> usize {if x != self.disj[x] {let par = self.disj[x];let r = self.root(par);self.disj[x] = r;}self.disj[x]}fn unite(&mut self, x: usize, y: usize) {let mut x = self.root(x);let mut y = self.root(y);if x == y { return }if self.rank[x] > self.rank[y] {std::mem::swap(&mut x, &mut y);}self.disj[x] = y;self.rank[y] += self.rank[x];}#[allow(unused)]fn is_same_set(&mut self, x: usize, y: usize) -> bool {self.root(x) == self.root(y)}#[allow(unused)]fn size(&mut self, x: usize) -> usize {let x = self.root(x);self.rank[x]}}// Verified by https://atcoder.jp/contests/arc084/submissions/3935443#[derive(Clone)]struct BitSet {size: usize,buf: Vec<usize>,}impl BitSet {// size should be a multiple of bit-size of usize.fn new(size: usize) -> Self {let w = 8 * std::mem::size_of::<usize>();assert_eq!(size & (w - 1), 0);let count = size / w;BitSet {size: size,buf: vec![0; count],}}#[allow(unused)]fn set(&mut self, idx: usize, val: bool) {debug_assert!(idx < self.size);let w = 8 * std::mem::size_of::<usize>();let idx0 = idx / w;let idx1 = idx & (w - 1);if val {self.buf[idx0] |= 1 << idx1;} else {self.buf[idx0] &= !(1 << idx1);}}#[allow(unused)]fn get(&self, idx: usize) -> bool {let w = 8 * std::mem::size_of::<usize>();debug_assert!(idx < self.size);let idx0 = idx / w;let idx1 = idx & (w - 1);(self.buf[idx0] >> idx1 & 1) == 1}#[allow(unused)]fn shl(&self, val: usize) -> Self {if val >= self.size { return Self::new(self.size); }let w = 8 * std::mem::size_of::<usize>();let count = self.size / w;let sh0 = val / w;let sh1 = val & (w - 1);let mut ans = Self::new(self.size);if sh1 == 0 {for i in 0 .. count - sh0 {ans.buf[i + sh0] = self.buf[i];}} else {ans.buf[sh0] = self.buf[0] << sh1;for i in 1 .. count - sh0 {ans.buf[i + sh0] = self.buf[i] << sh1| self.buf[i - 1] >> (w - sh1);}}ans}// Not verified#[allow(unused)]fn shr(&self, val: usize) -> Self {if val >= self.size { return Self::new(self.size); }let w = 8 * std::mem::size_of::<usize>();let count = self.size / w;let sh0 = val / w;let sh1 = val & (w - 1);let mut ans = Self::new(self.size);if sh1 == 0 {for i in 0 .. count - sh0 {ans.buf[i] = self.buf[i + sh0];}} else {for i in 0 .. count - sh0 - 1 {ans.buf[i] = self.buf[i + sh0] >> sh1| self.buf[i + sh0 + 1] << (w - sh1);}ans.buf[self.size - sh0 - 1] = self.buf[self.size - 1] >> sh1;}ans}#[allow(unused)]fn msb(&self) -> Option<usize> {let w = 8 * std::mem::size_of::<usize>();let count = self.size / w;for i in (0 .. count).rev() {let v = self.buf[i];if v != 0 {return Some(w * i + w - 1 - v.leading_zeros() as usize);}}None}}// TODO reference is not allowed as rhsimpl std::ops::BitXorAssign for BitSet {fn bitxor_assign(&mut self, other: BitSet) {debug_assert_eq!(self.size, other.size);for i in 0 .. self.buf.len() {unsafe {*self.buf.get_unchecked_mut(i) ^= *other.buf.get_unchecked(i);}}}}impl std::ops::BitOrAssign for BitSet {fn bitor_assign(&mut self, other: BitSet) {debug_assert_eq!(self.size, other.size);for i in 0 .. self.buf.len() {unsafe {*self.buf.get_unchecked_mut(i) |= *other.buf.get_unchecked(i);}}}}impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet {fn bitor_assign(&mut self, other: &BitSet) {debug_assert_eq!(self.size, other.size);for i in 0 .. self.buf.len() {unsafe {*self.buf.get_unchecked_mut(i) |= *other.buf.get_unchecked(i);}}}}// Tags: diameter-of-graphs// The author read the editorial before implementing this.// https://yukicoder.me/problems/no/1400// O(N^3/64)fn main() {input! {n: usize, d: i64,e: [chars; n],}const W: usize = 2048;let mut bs = vec![BitSet::new(W); n];let mut uf = UnionFind::new(2 * n);for i in 0..n {for j in 0..n {if e[i][j] == '1' {bs[i].set(j, true);uf.unite(i, j + n);}}}if uf.size(0) != 2 * n {println!("No");return;}let d = std::cmp::min(n as i64, d / 2) * 2 + (d % 2);let mut mat2 = vec![BitSet::new(W); n];for i in 0..n {for j in 0..n {if bs[i].get(j) {mat2[i] |= &bs[j];}}}// O(n^3/64)for i in 0..n {let mut r = BitSet::new(W);r.set(i, true);let mut v = vec![i];for _ in 0..d / 2 {if v.is_empty() { break; }let mut nr = r.clone();for k in v.drain(..) {if r.get(k) {nr |= &mat2[k];}}let mut diff = nr.clone();diff ^= r;r = nr;for k in 0..diff.buf.len() {if diff.buf[k] != 0 {for l in 0..64 { // only for 64-bit envv.push(64 * k + l);}}}}if d % 2 == 1 {let mut nr = BitSet::new(W);for k in 0..n {if r.get(k) {nr |= &bs[k];}}r = nr;}if !(0..n).all(|p| r.get(p)) {println!("No");return;}}println!("Yes");}