#780378 (Rust) No.2020 Sum of Common Prefix Length

提出ソース

結果

問題	No.2020 Sum of Common Prefix Length
ユーザー	akakimidori
提出日時	2022-07-22 21:39:02
言語	Rust (1.77.0)
結果	AC
実行時間	285 ms / 2,000 ms
コード長	10,978 bytes
コンパイル時間	5,446 ms
コンパイル使用メモリ	162,808 KB
実行使用メモリ	84,912 KB
最終ジャッジ日時	2023-09-17 09:15:30
合計ジャッジ時間	12,379 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	53 ms 14,044 KB
testcase_08	AC	55 ms 13,504 KB
testcase_09	AC	55 ms 14,292 KB
testcase_10	AC	55 ms 15,068 KB
testcase_11	AC	58 ms 14,340 KB
testcase_12	AC	56 ms 13,548 KB
testcase_13	AC	58 ms 14,320 KB
testcase_14	AC	62 ms 14,212 KB
testcase_15	AC	86 ms 34,556 KB
testcase_16	AC	88 ms 34,836 KB
testcase_17	AC	150 ms 42,032 KB
testcase_18	AC	129 ms 31,656 KB
testcase_19	AC	138 ms 33,552 KB
testcase_20	AC	220 ms 84,912 KB
testcase_21	AC	264 ms 77,868 KB
testcase_22	AC	261 ms 73,468 KB
testcase_23	AC	260 ms 72,500 KB
testcase_24	AC	283 ms 83,316 KB
testcase_25	AC	285 ms 82,260 KB
testcase_26	AC	106 ms 48,544 KB
testcase_27	AC	1 ms 4,380 KB
testcase_28	AC	66 ms 20,516 KB
testcase_29	AC	65 ms 21,340 KB
testcase_30	AC	65 ms 21,452 KB
testcase_31	AC	177 ms 79,300 KB
testcase_32	AC	173 ms 83,088 KB
testcase_33	AC	133 ms 50,476 KB
testcase_34	AC	113 ms 30,196 KB
testcase_35	AC	110 ms 29,844 KB
testcase_36	AC	149 ms 54,804 KB
testcase_37	AC	128 ms 39,128 KB

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

コンパイルメッセージ

warning: unused variable: `s`
   --> Main.rs:305:25
    |
305 |     let s = (0..n).map(|s| sc.next_bytes()).collect::<Vec<_>>();
    |                         ^ help: if this is intentional, prefix it with an underscore: `_s`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: 1 warning emitted

ソースコード

raw source code

// ---------- begin SegmentTree Range update Point query ----------
mod segment_tree {
    pub struct RUPQ<T, F> {
        size: usize,
        bit: usize,
        data: Vec<T>,
        e: T,
        op: F,
    }
    impl<T, F> RUPQ<T, F>
    where
        T: Clone,
        F: Fn(&T, &T) -> T,
    {
        pub fn new(size: usize, e: T, op: F) -> Self {
            let size = size.next_power_of_two();
            let bit = size.trailing_zeros() as usize;
            Self {
                size,
                bit,
                data: vec![e.clone(); 2 * size],
                e,
                op,
            }
        }
        pub fn find(&self, x: usize) -> T {
            assert!(x < self.size);
            let mut x = x + self.size;
            let mut ans = self.data[x].clone();
            while x > 1 {
                x >>= 1;
                ans = (self.op)(&ans, &self.data[x]);
            }
            ans
        }
        fn propagate(&mut self, x: usize) {
            let f = std::mem::replace(&mut self.data[x], self.e.clone());
            self.data[2 * x] = (self.op)(&self.data[2 * x], &f);
            self.data[2 * x + 1] = (self.op)(&self.data[2 * x + 1], &f);
        }
        pub fn update(&mut self, l: usize, r: usize, f: T) {
            assert!(l <= r && r <= self.size);
            if l == r {
                return;
            }
            let mut l = l + self.size;
            let mut r = r + self.size;
            for i in (1..=self.bit).rev() {
                if (l >> i) << i != l {
                    self.propagate(l >> i);
                }
                if (r >> i) << i != r {
                    self.propagate((r - 1) >> i);
                }
            }
            while l < r {
                if l & 1 == 1 {
                    self.data[l] = (self.op)(&self.data[l], &f);
                    l += 1;
                }
                if r & 1 == 1 {
                    r -= 1;
                    self.data[r] = (self.op)(&self.data[r], &f);
                }
                l >>= 1;
                r >>= 1;
            }
        }
    }
}
// ---------- end SegmentTree Range update Point query ----------
// ---------- begin Heavy-Light decomposition ----------
pub struct HLD {
    size: usize,
    edge: Vec<(usize, usize)>,
    child: Vec<Vec<usize>>,
    path_root: Vec<usize>,
    parent: Vec<usize>,
    left: Vec<usize>,
    right: Vec<usize>,
    inverse: Vec<usize>,
}

impl HLD {
    pub fn new(size: usize) -> Self {
        assert!(size <= 10usize.pow(8));
        HLD {
            size: size,
            edge: Vec::with_capacity(size - 1),
            child: Vec::new(),
            path_root: Vec::new(),
            parent: Vec::new(),
            left: Vec::new(),
            right: Vec::new(),
            inverse: Vec::new(),
        }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        assert!(a != b && a < self.size && b < self.size);
        self.edge.push((a, b));
    }
    pub fn build(&mut self, root: usize) {
        assert!(self.edge.len() + 1 == self.size);
        let size = self.size;
        let mut cnt = vec![0; size];
        for &(a, b) in self.edge.iter() {
            cnt[a] += 1;
            cnt[b] += 1;
        }
        let mut child = cnt
            .into_iter()
            .map(|c| Vec::with_capacity(c))
            .collect::<Vec<_>>();
        for &(a, b) in self.edge.iter() {
            child[a].push(b);
            child[b].push(a);
        }
        let mut parent = vec![size; size];
        let mut q = Vec::with_capacity(size);
        q.push(root);
        parent[root] = root;
        for i in 0..size {
            let v = q[i];
            for u in child[v].clone() {
                assert!(parent[u] == size);
                parent[u] = v;
                child[u].retain(|e| *e != v);
                q.push(u);
            }
        }
        let mut sum = vec![1; size];
        for &v in q.iter().rev() {
            let child = &mut child[v];
            if !child.is_empty() {
                let (pos, _) = child.iter().enumerate().max_by_key(|p| sum[*p.1]).unwrap();
                child.swap(0, pos);
                sum[v] = 1 + child.iter().fold(0, |s, a| s + sum[*a]);
            }
        }
        let mut path_root = (0..size).collect::<Vec<_>>();
        let mut left = vec![0; size];
        let mut right = vec![0; size];
        let mut dfs = vec![(root, false)];
        let mut id = 0;
        while let Some((v, end)) = dfs.pop() {
            if end {
                right[v] = id;
                continue;
            }
            left[v] = id;
            id += 1;
            dfs.push((v, true));
            let child = &child[v];
            if !child.is_empty() {
                for &u in child[1..].iter() {
                    path_root[u] = u;
                    dfs.push((u, false));
                }
                let u = child[0];
                path_root[u] = path_root[v];
                dfs.push((u, false));
            }
        }
        let mut inverse = vec![size; size];
        for (i, l) in left.iter().enumerate() {
            inverse[*l] = i;
        }
        self.child = child;
        self.parent = parent;
        self.left = left;
        self.right = right;
        self.path_root = path_root;
        self.inverse = inverse;
    }
    pub fn lca(&self, mut a: usize, mut b: usize) -> usize {
        assert!(a < self.size && b < self.size);
        let path = &self.path_root;
        let parent = &self.parent;
        let index = &self.left;
        while path[a] != path[b] {
            if index[a] > index[b] {
                std::mem::swap(&mut a, &mut b);
            }
            b = parent[path[b]];
        }
        std::cmp::min((index[a], a), (index[b], b)).1
    }
    pub fn path(
        &self,
        src: usize,
        dst: usize,
        up: &mut Vec<(usize, usize)>,
        down: &mut Vec<(usize, usize)>,
    ) {
        assert!(src < self.size && dst < self.size);
        up.clear();
        down.clear();
        let path = &self.path_root;
        let parent = &self.parent;
        let index = &self.left;
        let mut x = src;
        let mut y = dst;
        while path[x] != path[y] {
            if index[x] > index[y] {
                let p = path[x];
                assert!(p == path[p]);
                up.push((index[p], index[x] + 1));
                x = parent[p];
            } else {
                let p = path[y];
                assert!(p == path[p]);
                down.push((index[p], index[y] + 1));
                y = parent[p];
            }
        }
        if index[x] <= index[y] {
            down.push((index[x], index[y] + 1));
        } else {
            up.push((index[y], index[x] + 1));
        }
        down.reverse();
    }
    pub fn sub_tree(&self, v: usize) -> (usize, usize) {
        assert!(v < self.size);
        (self.left[v], self.right[v])
    }
    pub fn parent(&self, v: usize) -> Option<usize> {
        assert!(v < self.size);
        let p = self.parent[v];
        if p == v {
            None
        } else {
            Some(p)
        }
    }
    // s -> t へのパスの2番目の頂点を返す
    pub fn next(&self, s: usize, t: usize) -> usize {
        assert!(s < self.size && t < self.size && s != t);
        let (a, b) = self.sub_tree(s);
        let (c, d) = self.sub_tree(t);
        if !(a <= c && d <= b) {
            return self.parent[s];
        }
        let mut pos = t;
        let mut pre = t;
        while self.path_root[s] != self.path_root[pos] {
            pre = self.path_root[pos];
            pos = self.parent[pre];
        }
        if s == pos {
            pre
        } else {
            self.child[s][0]
        }
    }
    pub fn vertex(&self, x: usize) -> usize {
        assert!(x < self.size);
        self.inverse[x]
    }
}
// ---------- end Heavy-Light decomposition ----------
// ---------- 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::io::Write;

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 n: usize = sc.next();
    let s = (0..n).map(|s| sc.next_bytes()).collect::<Vec<_>>();
    let mut ask = vec![];
    for (i, s) in s.iter().enumerate() {
        for &c in s.iter() {
            ask.push((1, i, c));
        }
    }
    let q: usize = sc.next();
    for _ in 0..q {
        let op = sc.next::<u8>();
        let x = sc.next::<usize>() - 1;
        let c = if op == 1 {
            sc.next_bytes()[0]
        } else {
            0
        };
        ask.push((op, x, c));
    }
    let op = ask;
    let mut g: Vec<Vec<(usize, u8)>> = vec![vec![]];
    {
        let mut s = vec![vec![]; n];
        for &(op, x, c) in op.iter() {
            if op == 1 {
                s[x].push(c);
            }
        }
        for s in s {
            let mut pos = 0;
            for &c in s.iter() {
                if g[pos].iter().all(|e| e.1 != c) {
                    let v = g.len();
                    g.push(vec![]);
                    g[pos].push((v, c));
                }
                pos = g[pos].iter().find(|e| e.1 == c).unwrap().0;
            }
        }
    }
    let mut hld = HLD::new(g.len());
    let root = 0;
    for (i, c) in g.iter().enumerate() {
        for &(u, _) in c.iter() {
            hld.add_edge(i, u);
        }
    }
    hld.build(root);
    let mut seg = segment_tree::RUPQ::new(g.len(), 0u64, |a, b| *a + *b);
    let mut pos = vec![0; n];
    for (op, x, c) in op {
        let pos = &mut pos[x];
        if op == 2 {
            let ans = seg.find(hld.sub_tree(*pos).0);
            writeln!(out, "{}", ans).ok();
        } else {
            *pos = g[*pos].iter().find(|e| e.1 == c).unwrap().0;
            let (l, r) = hld.sub_tree(*pos);
            seg.update(l, r, 1);
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード