結果
| 問題 | No.2981 Pack Tree into Grid |
| ユーザー |
 akakimidori
|
| 提出日時 | 2024-12-05 04:42:48 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 970 ms / 2,000 ms |
| コード長 | 10,268 bytes |
| コンパイル時間 | 15,674 ms |
| コンパイル使用メモリ | 379,116 KB |
| 実行使用メモリ | 24,612 KB |
| 最終ジャッジ日時 | 2024-12-05 04:43:09 |
| 合計ジャッジ時間 | 19,835 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
コンパイルメッセージ
warning: type alias `Set` is never used
--> src/main.rs:204:6
|
204 | type Set<T> = BTreeSet<T>;
| ^^^
|
= note: `#[warn(dead_code)]` on by default
warning: type alias `Deque` is never used
--> src/main.rs:205:6
|
205 | type Deque<T> = VecDeque<T>;
| ^^^^^
ソースコード
// ---------- begin mod vector ----------mod modvector {const MOD: u64 = (1u64 << 61) - 1;#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]struct ModInt(u64);impl std::ops::Add for ModInt {type Output = Self;fn add(self, rhs: Self) -> Self::Output {debug_assert!(self.0 < MOD && rhs.0 < MOD);let mut d = self.0 + rhs.0;if d >= MOD {d -= MOD;}ModInt(d)}}impl std::ops::Sub for ModInt {type Output = Self;fn sub(self, rhs: Self) -> Self::Output {debug_assert!(self.0 < MOD && rhs.0 < MOD);let mut d = self.0 + MOD - rhs.0;if d >= MOD {d -= MOD;}ModInt(d)}}impl std::ops::Mul for ModInt {type Output = Self;fn mul(self, rhs: Self) -> Self::Output {debug_assert!(self.0 < MOD && rhs.0 < MOD);let v = self.0 as u128 * rhs.0 as u128;let mut c = (v >> 61) as u64 + (v & MOD as u128) as u64;if c >= MOD {c -= MOD;}ModInt(c)}}impl ModInt {fn new(v: u64) -> Self {ModInt(v % MOD)}fn zero() -> Self {ModInt(0)}fn pow(&self, n: u64) -> Self {let mut t = ModInt(1);let mut s = *self;let mut n = n;while n > 0 {if n & 1 == 1 {t = t * s;}s = s * s;n >>= 1;}t}fn inv(&self) -> Self {assert!(self.0 > 0);self.pow(MOD - 2)}}#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]pub struct ModVector<const N: usize> {val: [ModInt; N],}#[allow(dead_code)]impl<const N: usize> ModVector<N> {pub fn zero() -> Self {ModVector {val: [ModInt::zero(); N],}}pub fn one() -> Self {ModVector {val: [ModInt::new(1); N],}}pub fn new(v: &[u64]) -> Self {assert!(v.len() >= N);let mut ans = ModVector::zero();for (x, a) in ans.val.iter_mut().zip(v.iter()) {*x = ModInt::new(*a);}ans}pub fn single(v: u64) -> Self {ModVector::new(&[v; N])}pub fn add(&self, rhs: &Self) -> Self {let mut ans = ModVector::zero();for (c, (a, b)) in ans.val.iter_mut().zip(self.val.iter().zip(rhs.val.iter())) {*c = *a + *b;}ans}pub fn sub(&self, rhs: &Self) -> Self {let mut ans = ModVector::zero();for (c, (a, b)) in ans.val.iter_mut().zip(self.val.iter().zip(rhs.val.iter())) {*c = *a - *b;}ans}pub fn mul(&self, rhs: &Self) -> Self {let mut ans = ModVector::zero();for (c, (a, b)) in ans.val.iter_mut().zip(self.val.iter().zip(rhs.val.iter())) {*c = *a * *b;}ans}pub fn inv(&self) -> Self {let mut ans = ModVector::zero();for (x, a) in ans.val.iter_mut().zip(self.val.iter()) {*x = a.inv();}ans}pub fn generate_random_rad() -> Self {let mut rad = ModVector::zero();for (i, v) in rad.val.iter_mut().enumerate() {*v = ModInt::new(if i & 1 == 0 {rand_time() as u64 + 2} else {rand_memory() as u64 + 2});}rad}}pub fn rand_time() -> u32 {static mut X: u32 = 0;unsafe {if X == 0 {use std::time::{SystemTime, UNIX_EPOCH};X = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().subsec_nanos();}X ^= X << 13;X ^= X >> 17;X ^= X << 5;X}}pub fn rand_memory() -> u32 {static mut X: u32 = 0;unsafe {if X == 0 {X = Box::into_raw(Box::new("I hope this is a random number")) as u32;}X ^= X << 13;X ^= X >> 17;X ^= X << 5;X}}}// ---------- end mod vector ----------// ---------- begin scannner ----------#[allow(dead_code)]mod scanner {use std::str::FromStr;pub struct Scanner<'a> {it: std::str::SplitWhitespace<'a>,}impl<'a> Scanner<'a> {pub fn new(s: &'a String) -> Scanner<'a> {Scanner {it: s.split_whitespace(),}}pub fn next<T: FromStr>(&mut self) -> T {self.it.next().unwrap().parse::<T>().ok().unwrap()}pub fn next_bytes(&mut self) -> Vec<u8> {self.it.next().unwrap().bytes().collect()}pub fn next_chars(&mut self) -> Vec<char> {self.it.next().unwrap().chars().collect()}pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {(0..len).map(|_| self.next()).collect()}}}// ---------- end scannner ----------use std::collections::*;use std::io::Write;type Map<K, V> = BTreeMap<K, V>;type Set<T> = BTreeSet<T>;type Deque<T> = VecDeque<T>;fn main() {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut sc = scanner::Scanner::new(&s);let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());run(&mut sc, &mut out);}fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {let t: u32 = sc.next();for _ in 0..t {let n: usize = sc.next();let mut e = vec![(0, 0, 0); n - 1];for e in e.iter_mut() {e.0 = sc.next::<usize>() - 1;e.1 = sc.next::<usize>() - 1;e.2 = sc.next::<usize>();}let h: usize = sc.next();let _w: usize = sc.next();let s = (0..h).map(|_| sc.next_bytes()).collect::<Vec<_>>();if let Some(ans) = solve(e, s) {writeln!(out, "Yes").ok();for (a, b) in ans {writeln!(out, "{} {}", a + 1, b + 1).ok();}} else {writeln!(out, "No").ok();}}}type M = modvector::ModVector<2>;fn solve(e: Vec<(usize, usize, usize)>, s: Vec<Vec<u8>>) -> Option<Vec<(usize, usize)>> {let n = e.len() + 1;let (v, e) = {let mut id = n;let mut edge = vec![];for (a, b, w) in e {let mut v = vec![a];for _ in 1..w {v.push(id);id += 1;}v.push(b);edge.extend(v.windows(2).map(|v| (v[0], v[1])));}(id, edge)};let (memo, u, f) = {let mut id = 0;let h = s.len();let w = s[0].len();let mut v = vec![vec![!0; w]; h];for (v, s) in v.iter_mut().zip(s.iter()) {for (v, s) in v.iter_mut().zip(s.iter()) {if *s == b'#' {*v = id;id += 1;}}}let mut edge = vec![];for i in 0..h {for j in 0..w {if i > 0 && v[i][j] < id && v[i - 1][j] < id {edge.push((v[i][j], v[i - 1][j]));}if j > 0 && v[i][j] < id && v[i][j - 1] < id {edge.push((v[i][j], v[i][j - 1]));}}}(v, id, edge)};let dep = (0..v.max(u)).map(|_| M::generate_random_rad()).collect::<Vec<_>>();let mut g = vec![vec![]; v];let mut h = vec![vec![]; u];for &(a, b) in e.iter() {g[a].push(b);g[b].push(a);}for &(a, b) in f.iter() {h[a].push(b);h[b].push(a);}let mut dp = Map::new();let hash = calc(0, 0, &g, &dep, &mut dp);(0..u).find(|&u| calc(u, u, &h, &dep, &mut dp) == hash).map(|root| {let mut inv_memo = Map::new();for (i, memo) in memo.iter().enumerate() {for (j, memo) in memo.iter().enumerate() {inv_memo.insert(*memo, (i, j));}}let mut res = vec![(0, 0); v];let mut dfs = vec![(0, 0, root, root)];while let Some((v, p, u, q)) = dfs.pop() {res[v] = inv_memo[&u];let mut hist = Map::new();for &a in g[v].iter().filter(|a| **a != p) {hist.entry(calc(a, v, &g, &dep, &mut dp)).or_insert(vec![]).push(a);}for &b in h[u].iter().filter(|a| **a != q) {let a = hist.entry(calc(b, u, &h, &dep, &mut dp)).or_insert(vec![]).pop().unwrap();dfs.push((a, v, b, u));}}res.truncate(n);res})}// (v, p, g), (depth, hash)fn calc(v: usize,p: usize,g: &[Vec<usize>],depth: &[M],dp: &mut Map<(usize, usize, *const [Vec<usize>]), (usize, M)>,) -> (usize, M) {if let Some(&(d, h)) = dp.get(&(v, p, g)) {return (d, h);}let mut val = M::one();let mut k = 0usize;for &u in g[v].iter().filter(|e| **e != p) {let (a, b) = calc(u, v, g, depth, dp);val = val.mul(&b);k = k.max(a + 1);}val = val.add(&depth[k]);dp.insert((v, p, g), (k, val));(k, val)}