#1030021 (Rust) No.2981 Pack Tree into Grid

提出ソース

結果

問題	No.2981 Pack Tree into Grid
ユーザー	akakimidori
提出日時	2024-12-05 04:59:15
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	20 ms / 2,000 ms
コード長	10,340 bytes
コンパイル時間	16,017 ms
コンパイル使用メモリ	379,104 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-12-05 04:59:33
合計ジャッジ時間	17,145 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	12 ms 5,248 KB
testcase_02	AC	12 ms 5,248 KB
testcase_03	AC	13 ms 5,248 KB
testcase_04	AC	13 ms 5,248 KB
testcase_05	AC	14 ms 5,248 KB
testcase_06	AC	10 ms 5,248 KB
testcase_07	AC	10 ms 5,248 KB
testcase_08	AC	10 ms 5,248 KB
testcase_09	AC	11 ms 5,248 KB
testcase_10	AC	13 ms 5,248 KB
testcase_11	AC	13 ms 5,248 KB
testcase_12	AC	13 ms 5,248 KB
testcase_13	AC	13 ms 5,248 KB
testcase_14	AC	13 ms 5,248 KB
testcase_15	AC	12 ms 5,248 KB
testcase_16	AC	11 ms 5,248 KB
testcase_17	AC	12 ms 5,248 KB
testcase_18	AC	12 ms 5,248 KB
testcase_19	AC	12 ms 5,248 KB
testcase_20	AC	12 ms 5,248 KB
testcase_21	AC	14 ms 5,248 KB
testcase_22	AC	20 ms 5,248 KB
testcase_23	AC	5 ms 5,248 KB
testcase_24	AC	12 ms 5,248 KB
testcase_25	AC	5 ms 5,248 KB
testcase_26	AC	5 ms 5,248 KB
testcase_27	AC	1 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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>;
    |      ^^^^^

ソースコード

raw source code

// ---------- 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)
    };
    if u != v {
        return None;
    }
    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 (g, h) = (&g, &h);
    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<Vec<usize>>,
    depth: &[M],
    dp: &mut Map<(usize, usize, *const Vec<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)
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード