Problem D: Road to Nutella

road_to_nutella.rs

// Robert on X: https://x.com/robertkingNZ
// Video walkthrough of solution: https://youtu.be/p2L-uvMlFaE?si=9PU_dHG4uDyPFQZz
// Problem statement: https://www.facebook.com/codingcompetitions/hacker-cup/2023/practice-round/problems/D

use std::thread;
use std::collections::{HashSet, VecDeque};
use std::io::{StdinLock, StdoutLock};
use segment_tree::SegmentPoint;
use segment_tree::ops::Min;

pub mod lca {
    const MAX_PARENT: usize = 1 << 50;
    pub struct LowestCommonAncestor {
        parent: Vec<Vec<usize>>,
        pub depth: Vec<usize>,
        log_v: usize,
    }

    impl LowestCommonAncestor {
        pub fn new(graph: &[Vec<usize>]) -> Self {
            let num_v = graph.len();
            let root = 0;
            let mut depth = vec![0; num_v];

            let mut log_v = 1;
            let mut i = 1;
            while i <= num_v {
                i *= 2;
                log_v += 1;
            }
            let mut parent: Vec<Vec<usize>> = vec![vec![0; num_v]; log_v];

            let mut depth_vis = vec![false; num_v];
            let mut stack = ::std::collections::VecDeque::new();
            stack.push_front(root);
            parent[0][root] = MAX_PARENT;
            depth[root] = 0;
            depth_vis[root] = true;
            while !stack.is_empty() {
                let v = stack.pop_front().unwrap();
                stack.push_front(v);
                for &u in &graph[v] {
                    if depth_vis[u] {
                        continue;
                    }
                    parent[0][u] = v;
                    depth[u] = depth[v] + 1;
                    depth_vis[u] = true;
                    stack.push_front(u);
                }

                let head = stack.pop_front().unwrap();
                if head != v {
                    stack.push_front(head);
                }
            }

            for k in 0..(log_v - 1) {
                for u in 0..num_v {
                    parent[k + 1][u] = if parent[k][u] == MAX_PARENT {
                        MAX_PARENT
                    } else {
                        parent[k][parent[k][u]]
                    };
                }
            }

            LowestCommonAncestor {
                parent,
                depth,
                log_v,
            }
        }

        pub fn get_lca(&self, u: usize, v: usize) -> usize {
            let (mut u, mut v) = if self.depth[u] <= self.depth[v] {
                (u, v)
            } else {
                (v, u)
            };
            for k in 0..self.log_v {
                if ((self.depth[v] - self.depth[u]) & (1 << k)) != 0 {
                    v = self.parent[k][v];
                }
            }
            if u == v {
                return u;
            }

            for k in (0..self.log_v).rev() {
                if self.parent[k][u] != self.parent[k][v] {
                    u = self.parent[k][u];
                    v = self.parent[k][v];
                }
            }
            self.parent[0][u]
        }

        pub fn get_dist(&self, u: usize, v: usize) -> usize {
            let lca = self.get_lca(u, v);
            self.depth[u] + self.depth[v] - self.depth[lca] * 2
        }
    }
}

pub struct BridgeDetector {
    articulations: Vec<usize>,
    bridges: Vec<(usize, usize)>,
    visit: Vec<bool>,
    order: Vec<usize>,
    low_link: Vec<usize>,
    k: usize,
}

impl BridgeDetector {
    pub fn new(graph: &[Vec<usize>]) -> Self {
        let n = graph.len();
        let mut d = BridgeDetector {
            articulations: vec![],
            bridges: vec![],
            visit: vec![false; n],
            order: vec![0; n],
            low_link: vec![0; n],
            k: 0,
        };
        d.run(graph);
        d
    }

    fn run(&mut self, graph: &[Vec<usize>]) {
        let n = graph.len();
        for i in 0..n {
            if !self.visit[i] {
                self.dfs(i, 0, graph, i);
            }
        }
    }

    fn dfs(&mut self, v: usize, previous: usize, graph: &[Vec<usize>], root: usize) {
        self.visit[v] = true;
        self.order[v] = self.k;
        self.k += 1;
        self.low_link[v] = self.order[v];

        let mut is_articulation = false;
        let mut dimension = 0;
        for &next in graph[v].iter() {
            if !self.visit[next] {
                // The edge (v->next) is not a backedge.
                dimension += 1;
                self.dfs(next, v, graph, root);
                self.low_link[v] = std::cmp::min(self.low_link[v], self.low_link[next]);
                if v != root && self.order[v] <= self.low_link[next] {
                    is_articulation = true;
                }
                if self.order[v] < self.low_link[next] {
                    let min = std::cmp::min(v, next);
                    let max = std::cmp::max(v, next);
                    self.bridges.push((min, max));
                }
            } else if v == root || next != previous {
                // The edge (v->next) is a back-edge.
                self.low_link[v] = std::cmp::min(self.low_link[v], self.order[next]);
            }
        }

        if v == root && dimension > 1 {
            is_articulation = true;
        }
        if is_articulation {
            self.articulations.push(v);
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

fn bfs_component(g: &Vec<Vec<usize>>, cur: usize, count: usize, component: &mut Vec<Option<usize>>, depth: &mut Vec<Option<usize>>) {
    let mut q = VecDeque::new();
    q.push_back((cur, 0));
    component[cur] = Some(count);
    depth[cur] = Some(0);
    while let Some((cur, d)) = q.pop_front() {
        for &child in &g[cur] {
            if component[child].is_none() {
                depth[child] = Some(d+1);
                component[child] = Some(count);
                q.push_back((child, d+1));
            }
        }
    }
}

fn get_components(non_bridge_edges: Vec<(usize, usize)>, n: usize) -> (Vec<bool>, Vec<usize>) {
    let mut g = vec![vec![]; n];
    let mut component: Vec<Option<usize>> = vec![None; g.len()];
    let mut depth: Vec<Option<usize>> = vec![None; g.len()];
    let mut count = 0;
    for e in &non_bridge_edges {
        g[e.0].push(e.1);
        g[e.1].push(e.0);
    }
    for node in 0..n {
        if component[node].is_none() {
            bfs_component(&g, node, count, &mut component, &mut depth);
            count += 1;
        }
    }
    let mut odd = vec![false; count];
    for e in &non_bridge_edges {
        let d1 = depth[e.0].unwrap();
        let d2 = depth[e.1].unwrap();
        if d1 % 2 == d2 % 2 {
            odd[component[e.0].unwrap()] = true;
        }
    }
    (odd, component.into_iter().map(|c| c.unwrap()).collect())
}

fn read_graph(sc: &mut IO<StdinLock, StdoutLock>) -> (Vec<(usize, usize)>,Vec<Vec<usize>>) {
    let n = sc.read();
    let m = sc.read();
    let mut edges = Vec::with_capacity(m);
    for _ in 0..m {
        let u: usize = sc.read();
        let v: usize = sc.read();
        edges.push((u-1, v-1));
    }
    let mut g = vec![vec![]; n];
    for e in &edges {
        g[e.0].push(e.1);
        g[e.1].push(e.0);
    }
    (edges, g)
}

#[derive(Debug)]
struct Query {
    u: usize,
    v: usize,
    cu: usize,
    cv: usize,
    lca: usize,
    ans: i64,
}

fn read_queries(sc: &mut IO<StdinLock, StdoutLock>) -> Vec<Query> {
    let q: usize = sc.read();
    let mut queries = Vec::with_capacity(q);
    for _ in 0..q {
        let u: usize = sc.read();
        let v: usize = sc.read();
        queries.push(Query{
            u: u-1,
            v: v-1,
            cu: 0,
            cv: 0,
            lca: 0,
            ans: i64::MAX,
        });
    }
    queries
}

fn dfs_g(g: &Vec<Vec<usize>>) -> Vec<(usize, usize)> {
    let mut stack = vec![0];
    let mut visited = vec![false; g.len()];
    visited[0] = true;
    let mut edges = vec![];
    while let Some(node) = stack.pop() {
        for &child in &g[node] {
            if !visited[child] {
                visited[child] = true;
                edges.push((node, child));
                stack.push(child);
            }
        }
    }
    edges
}

fn dfs_cost_below(tree: &Vec<Vec<usize>>, node: usize, cost: &mut Vec<i64>) {
    for &child in &tree[node] {
        dfs_cost_below(tree, child, cost);
        cost[node] = cost[node].min(cost[child].saturating_add(1));
    }
}

fn dfs_cost_above(tree: &Vec<Vec<usize>>, node: usize, cost: &mut Vec<i64>) {
    for &child in &tree[node] {
        cost[child] = cost[child].min(cost[node].saturating_add(1));
        dfs_cost_above(tree, child, cost);
    }
}

fn get_component_tree(sc: &mut IO<StdinLock, StdoutLock>) -> (Vec<Vec<usize>>, Vec<usize>, Vec<i64>) {
    let (edges, g) = read_graph(sc);
    let n = g.len();
    let bridge_edges: HashSet<(usize, usize)> = BridgeDetector::new(&g).bridges.into_iter().collect();
    let non_bridge_edges: Vec<(usize, usize)> = edges.iter().cloned().filter(|e| !bridge_edges.contains(e)).collect();
    let (odd, component) = get_components(non_bridge_edges, n);
    let mut tree = vec![vec![];odd.len()];
    for (u, v) in dfs_g(&g) {
        if component[u] != component[v] {
            tree[component[u]].push(component[v]);
        }
    }
    let mut cost: Vec<i64> = odd.into_iter().map(|ok| if ok { 0 } else { i64::MAX }).collect();
    dfs_cost_below(&tree, 0, &mut cost);
    dfs_cost_above(&tree, 0, &mut cost);
    (tree, component, cost)
}

fn dfs(tree: &Vec<Vec<usize>>, node: usize, cost: &Vec<i64>, segment_tree: &mut SegmentPoint<i64, Min>, level: &Vec<usize>, node_queries: &Vec<Vec<usize>>, queries: &mut Vec<Query>) {
    segment_tree.modify(level[node], cost[node]);
    for &i in &node_queries[node] {
        queries[i].ans = queries[i].ans.min(
            segment_tree.query(level[queries[i].lca], level[node] + 1)
        );
    }
    for &child in &tree[node] {
        dfs(tree, child, cost, segment_tree, level, node_queries, queries);
    }
}

fn solve(sc: &mut IO<StdinLock, StdoutLock>) -> i64 {
    let (tree, component, cost) = get_component_tree(sc);
    let mut queries = read_queries(sc);
    if !cost.contains(&0) {
        return -1 * queries.len() as i64;
    }
    let lca = lca::LowestCommonAncestor::new(&tree);
    let mut node_queries = vec![vec![]; tree.len()];
    for q in &mut queries {
        q.cu = component[q.u];
        q.cv = component[q.v];
        // q.lca = get_lca(&parent, q.cu, q.cv, &level);
        q.lca = lca.get_lca(q.cu, q.cv);
    }
    for (i, q) in queries.iter().enumerate() {
        node_queries[q.cu].push(i);
        node_queries[q.cv].push(i);
    }
    let mut segment_tree = SegmentPoint::build(vec![tree.len() as i64; tree.len()], Min);
    dfs(&tree, 0, &cost, &mut segment_tree, &lca.depth, &node_queries, &mut queries);
    queries.iter().map(|q| q.ans).sum::<i64>()
}

fn main() {
    thread::Builder::new()
        .stack_size(32 * 1024 * 1024) // 32 MB
        .spawn(|| {
            let (r, w) = (std::io::stdin(), std::io::stdout());
            let mut sc = IO::new(r.lock(), w.lock());

            let t: usize = sc.read();
            for case in 1..=t {
                let ans = solve(&mut sc);
                println!("Case #{case}: {ans}");
            }
        })
        .unwrap()
        .join()
        .unwrap();
}