Hypyt

warning: function `compute_line_optimal_set` is never used
   --> input/code.rs:429:4
    |
429 | fn compute_line_optimal_set(
    |    ^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 1 warning emitted

use std::{
    collections::{HashMap, HashSet},
    io::stdin,
    isize, usize,
};

type Query = (usize, usize, usize, usize);

fn q_itr(q: usize) -> impl Iterator<Item = Query> {
    (0..q).map(|_| {
        let mut ln = String::new();
        stdin().read_line(&mut ln).unwrap();
        let mut litr = ln.split_ascii_whitespace();
        let y1 = litr.next().unwrap().parse::<usize>().unwrap() - 1;
        let x1 = litr.next().unwrap().parse::<usize>().unwrap() - 1;
        let y2 = litr.next().unwrap().parse::<usize>().unwrap() - 1;
        let x2 = litr.next().unwrap().trim_end().parse::<usize>().unwrap() - 1;
        (x1, y1, x2, y2)
    })
}

fn main() {
    let mut l = String::new();
    stdin().read_line(&mut l).unwrap();
    let mut itr = l.split_ascii_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();
    let q: usize = itr.next().unwrap().trim_end().parse().unwrap();

    if n <= 10 && m <= 10 && q <= 10 {
        let mut sr: Vec<Vec<usize>> = Vec::with_capacity(n);
        let mut sc: Vec<Vec<usize>> = Vec::with_capacity(m);
        for _ in 0..n {
            sr.push(Vec::new());
        }
        for _ in 0..m {
            sc.push(Vec::new());
        }
        for i in 0..n {
            let mut ln = String::new();
            stdin().read_line(&mut ln).unwrap();
            for (j, c) in ln.chars().enumerate() {
                if c == '.' {
                    sr[i].push(j);
                    sc[j].push(i);
                }
            }
        }
        let queries: Vec<Query> = q_itr(q).collect();
        test_group1(&sc, &sr, &queries);
    } else {
        let mut sc: Vec<HashSet<usize>> = Vec::new();
        let mut sr: Vec<HashSet<usize>> = Vec::new();
        for _ in 0..n {
            sr.push(HashSet::new());
        }
        for _ in 0..m {
            sc.push(HashSet::new());
        }
        let mut r_ts: HashMap<(usize, usize), HashSet<usize>> = HashMap::new();
        let mut c_ts: HashMap<(usize, usize), HashSet<usize>> = HashMap::new();
        for i in 0..n {
            let mut ln = String::new();
            stdin().read_line(&mut ln).unwrap();
            for (j, c) in ln.chars().enumerate() {
                if c == '.' {
                    sr[i].insert(j);
                    sc[j].insert(i);
                }
            }
        }
        for i in 0..n {
            for j in 0..n {
                if r_ts.contains_key(&(j, i)) {
                    r_ts.insert((i, j), r_ts[&(j, i)].clone());
                } else {
                    r_ts.insert((i, j), HashSet::new());
                    for c in 0..m {
                        if sc[c].contains(&i) && sc[c].contains(&j) {
                            unsafe {
                                r_ts.get_mut(&(i, j)).unwrap_unchecked().insert(c);
                            }
                        }
                    }
                }
            }
        }
        for i in 0..m {
            for j in 0..m {
                if c_ts.contains_key(&(j, i)) {
                    c_ts.insert((i, j), c_ts[&(j, i)].clone());
                } else {
                    c_ts.insert((i, j), HashSet::new());
                    for c in 0..n {
                        if sr[c].contains(&i) && sr[c].contains(&j) {
                            unsafe {
                                c_ts.get_mut(&(i, j)).unwrap_unchecked().insert(c);
                            }
                        }
                    }
                }
            }
        }
        let queries: Vec<Query> = q_itr(q).collect();
        test_group2_5(n, m, &queries, &r_ts, &c_ts);
    }
}

fn test_group1(sc: &[Vec<usize>], sr: &[Vec<usize>], queries: &[Query]) {
    for q in queries {
        let d = tg1_qry(q, sc, sr);
        println!("{}", d);
    }
}

fn tg1_qry(q: &Query, sc: &[Vec<usize>], sr: &[Vec<usize>]) -> isize {
    let mut ae = HashMap::new();
    let mut v1 = Vec::new();
    let mut v2 = Vec::new();
    v1.push((q.0, q.1));
    let mut ce = &mut v1;
    let mut ne = &mut v2;
    let mut d = 0;
    while ce.len() > 0 {
        for e in ce.iter() {
            if e.0 == q.2 && e.1 == q.3 {
                return d;
            }
            for ny in &sc[e.0] {
                let el = (e.0, *ny);
                if !ae.contains_key(&el) {
                    ae.insert(el, true);
                    ne.push(el);
                }
            }
            for nx in &sr[e.1] {
                let el = (*nx, e.1);
                if !ae.contains_key(&el) {
                    ae.insert(el, true);
                    ne.push(el);
                }
            }
        }
        ce.clear();
        let tmp = ce;
        ce = ne;
        ne = tmp;
        d += 1;
    }
    return -1;
}

/*
 * Problem:
 * State: S(x,y)
 * Goal: S(x, y) = G(x2, y2)
 * Available options at S(x,y) = N(x,y)
 * Task: Find the path P(S1, S2, S3, ..., SN) with the minimum N
 *
 * Additional properties:
 * Property One: If S1 in S2N then S2 in S1N -> undirected graph, with Sk as the nodes
 * Property Two: SkN divided into two sets: one where x = Sk.x and the other where y = Sk.y
 * Property Three: Up to 2 * 10^5 queries made simultaneoously, instead of only one. I.e, need to
 * make heavy use of previous results.
 *
 * Possible solutions:
 * 1. Trivial algorithm for finding minimum path between two nodes in a given graph
 * 2. Well-known and more optimal algorithm for finding minimum path between two nodes in a given
 *    graph
 * 3. Hand-crafted algorithm also making use of the second property
 *
 *
 * BFS: O((nm + nm(n - 1 + m - 1))) = O(nmq(n + m - 1))
 *
 * Observations for the hardest setting of the hardest test group:
 * 1. q = 2*10^5. Therefore the time complexity for processing each individual query needs to be roughly O(1).
 * 2. A good way to accomplish this seems to be going through the grid first and generating some
 *    data which would allow something akin to a simple lookup from a table in order to process a given
 *    query.
 * 3. Total node count is mn = 250^2 = 62500. Thus the amount of node pairs is
 *    (250^2)^2 ~= 3.9 * 10^9. Processing through all of them would require too many cycles,
 *    and it is too many items to store in memory anyway, requiring a hashmap of over 4GB of memory.
 * 4. This data would have to exploit some redundancies in data storage derived from the
 *    regularities in the computation of the shortest path.
 * 5. Properties for a given query (xo, yo, xt, yt), where d represents the shortest path for that
 *    query:
 * 5.1 If xo = xt and yo = yt then d = 0.
 * 5.2 Travelling to a point (x2, y2) from a point (x1, y1) always takes only one step when one of x1 =
 *   x2 or y2 = y1 is true. This is because in that case, both points are safe rooms of a given row
 *   or column, and as per the definition of the problem, it always takes exactly one step to
 *   travel from a given safe room to a different safe room in the same row or column.
 * 5.3 If only one of xo = xt or yo = yt, then d = 1. (From 5.2)
 * 5.4 In the third case of xo != xt and yo != yt:
 *     5.4.1 For whatever form the shortest path takes, it must include as its 2nd last step transferring
 *     into the row or column of yt or xt respectively. This step must occur at some point because the
 *     path ends when x = xt and y = yt. This step must be the second last step because of 5.2.
 *     5.4.2 Two cases for the shortest path: A) a path that first leads into the same row as the
 *     target room B) a path that first leads into the same column as the target room.
 *     5.4.3 The shortest path is min(A, B) + 1. (From 5.4.2)
 *     5.4.4 The problem can be reformulated as travelling from a given row or column to a given target row or column respectively. (From 5.4.3)
 *     5.4.5 The cases of travelling from row to row and from column to column are symmetric,
 *     therefore WLOG let's consider the case of row to row (r1 = starting row, r2 = target row):
 *         1) d depends on the starting column within the row.
 *         2) There is a set of columns within a row for which d is lowest
 *         3) For any columns outside of that set, the shortest path is d + 1. (From 5.2)
 *         4) The shortest paths can thus be reduced without loss of information into just the
 *            d for the set of columns within the row for which the path is the shortest. Let's
 *            call this set the row's optimal set. (From 1 - 3)
 *         5) If the row has any columns along which the target row also has a safe room, then the
 *            row's optimal set is those columns and its d = 1.
 *         6) Otherwise, the shortest path from r1 to r2 must include travelling to one or multiple
 *            intermediate rows, where an intermediate row is defined to be a row to which it is
 *            possible to directly travel to from r1. Therefore in this case, the shortest path from
 *            r1 to r2 will be determined recursively by comparing the shortest
 *            paths of the various intermediate row options (need to also take into account the
 *            fact that different intermediate rows are accessible from different columns).
 *                6.1) For a given intermediate row, the shortest path through that intermediate
 *                  row is calculated as the sum of the shortest path to that row from r1 and from
 *                  there to r2. This is effectively an O(1) operation, as both of these term are
 *                  among the 250^2 optimal sets for row pairs that need to be calculated anyway.
 *                6.2) Comparing the value calculated as in 6.1 accross all 248 possible intermediate
 *                  rows and selecting the lowest one is thus O(250). Because this needs to be done
 *                  for all 250^2 row pairs, in total the whole computation of optimal sets for all
 *                  row pairs takes 250^3 ~= 1.6 * 10^7 cycles. This should be acceptable.
 *                6.3) In terms of the column dimension of the task, the optimal set of r1 to ri
 *                  row pair is by definition the same as the set of columns from which within r1
 *                  it is possible to directly travel in one step to ri. The optimal set of the
 *                  whole operation of travelling from r1 to r2 will be a subset of the optimal set
 *                  from r1 to ri, as if the starting column was outside of the optimal set of r1 to
 *                  ri, then that would only add an extra step to the path as it would be
 *                  required to travel to a column within the optimal set of r1 to ri
 *                  before doing anything else in order to be able to even travel to ri.
 *                  If the optimal sets of r1 to ri and ri to r2 have an intersection, then this
 *                  intersection will be the optimal set of r1 to r2, and the d of r1 to
 *                  r2 will be the d of r1 to ri + the d of ri to r2. If there is no
 *                  intersection, then the optimal set of r1 to r2 will simply be the same
 *                  as the optimal set of r1 to ri and the d will be that of the previous
 *                  case incremented by one.
 *         7) Since m, n = 250 and 250^2 = 62500, it is also entirely feasible to compute and store the
 *            optimal sets for every row pair in an array.
 *     5.4.6 Once the optimal sets for every row pair and every column pair have been computed and
 *     stored (before processing the queries), A and B can be computed simply by looking up the d
 *     stored for optimal set of the given row or column pair, and then incrementing that by 1 if
 *     the starting position within the row or column falls outside the optimal set.
 *     5.4.7 Thus every query can be processed in O(1) in this way.
 *     5.4.8 Worst case total cycles of the whole task implemented this way should be 2 * 250^3 + 4 * 10^5 ~= 3.2 * 10^7.
 *     Worst case total memory should be 2 * 250^2 * (sizeof([usize; 249]) + sizeof(usize)) = 250^3 * 16
 *     bytes = 2.5 * 10^8 bytes = 250 MB
 * */

// What does vp.len() == 0 mean?
struct LineOptimalSet {
    vp: HashSet<usize>,
    d: isize,
}

fn test_group2_5(
    n: usize,
    m: usize,
    queries: &[Query],
    r_ts: &HashMap<(usize, usize), HashSet<usize>>,
    c_ts: &HashMap<(usize, usize), HashSet<usize>>,
) {
    let mut row_os = HashMap::with_capacity(n * n);
    let mut column_os = HashMap::with_capacity(m * m);
    let mut r_ds = HashMap::with_capacity(n * n);
    let mut c_ds = HashMap::with_capacity(m * m);
    for i in 0..n {
        for j in 0..n {
            n_compute_line_optimal_set(n, i, j, &mut row_os, r_ts, &mut r_ds);
        }
    }
    for i in 0..m {
        for j in 0..m {
            n_compute_line_optimal_set(m, i, j, &mut column_os, c_ts, &mut c_ds);
        }
    }
    for q in queries {
        let d = tg2_5_qry(*q, &row_os, &column_os);
        println!("{}", d);
    }
}

/*
 * 1. Every edge in the path from r1 to r2 will either have weight 1 or 2. The first edge will always
 * have weight 1.
 * 2. An edge has weight 1 if its OSET intersects with the intersection of the OSETs of all the previous edges with
 *    weight 1 plus the last edge with weight 2 before those edges. Otherwise, the edge has weight 2. An edge with
 *    weight 2 always breaks of the weight 1 chain (in the sense that for every edge after an edge
 *    with weight 2, the edges before that weight 2 edge don't matter for the weight of the new
 *    edge), and potentially starts a new one.
 * 3. The first potential weight 1 chain starts with the very first edge of the path, which always
 *    has weight 1. Every future weight 1 chain starts with a weight 2 edge.
 * 4. For the first weight 1 chain, it can be replaced simply with a weight 1 edge connecting the
 *    first node in the path with the last node of the chain. If the chain has more than 1
 *    node, this always yields a strictly shorter path. For all subsequent weight 1 chains, all
 *    the weight 1 edges can be removed entirely, and the weight 2 edge preceding the weight 1
 *    chain be replaced with a weight 2 edge leading directly to the last node in the weight 1
 *    chain. This is always strictly faster, even if there is only one node in the weight 1
 *    chain.
 * 5. For a path which is among those with the least distance between r1 and r2, there can be no
 *    edges with weight 1 in any place except the very first edge of the path, which always must
 *    have weight 1.
 * 6. The optimal set of every path is simply the optimal set of the transition between r1 and the
 *    first intermediate node. The distance of the path is simply 2(n - 2) + 1 = 2n - 3, where n
 *    is the number of nodes.
 * 7. The shortest path is simply determined by the path with the least amount of nodes.
 * 8. Any algorithm which finds the path with the least number of nodes will never output any paths
 *    which contain any weight 1 edges beyond the first edge in the path, as in those cases the
 *    number of nodes could be reduced as outlined in (4).
 * 9. The problem is thus reduced to a standard problem of finding the path with the least nodes,
 *    with one important catch: it is required to also find all other paths with the same distance
 *    as the path with the shortest distance, in order to fully determine the optimal set of the
 *    shortest path.
 * 10. Only those paths where the 2nd node (i.e, the first intermediate node) differs are required.
 *
 * */
fn bfs_los(
    n: usize,
    l1: usize,
    l2: usize,
    l_ts: &HashMap<(usize, usize), HashSet<usize>>,
    ds: &mut HashMap<(usize, usize), isize>,
) -> isize {
    let l1_2 = (l1, l2);
    if ds.contains_key(&l1_2) {
        return ds[&l1_2];
    }
    let mut alr_explored = HashSet::new();
    let mut v1 = Vec::new();
    let mut v2 = Vec::new();
    let mut ce = &mut v1;
    let mut ne = &mut v2;
    ce.push(l1);
    let mut d = 0;
    while ce.len() > 0 {
        for &e in ce.iter() {
            if e == l2 {
                ds.insert(l1_2, d);
                return d;
            }
            for li in 0..n {
                let lp1_i = (e, li);
                if l_ts[&lp1_i].len() == 0 {
                    continue;
                }
                if !alr_explored.contains(&li) {
                    ne.push(li);
                    alr_explored.insert(li);
                }
            }
        }
        ce.clear();
        let tmp = ce;
        ce = ne;
        ne = tmp;
        d += 1;
    }
    ds.insert(l1_2, -1);
    return -1;
}

fn n_compute_line_optimal_set(
    n: usize,
    l1: usize,
    l2: usize,
    line_os: &mut HashMap<(usize, usize), LineOptimalSet>,
    l_ts: &HashMap<(usize, usize), HashSet<usize>>,
    ds: &mut HashMap<(usize, usize), isize>,
) {
    if line_os.contains_key(&(l1, l2)) {
        return;
    }
    let lp12 = (l1, l2);
    let vp = &l_ts[&lp12];
    if vp.len() > 0 {
        line_os.insert(
            lp12,
            LineOptimalSet {
                d: 1,
                vp: vp.clone(),
            },
        );
        return;
    } else {
        let mut lis = Vec::new();
        let mut sd = isize::MAX - 1;
        for li in 0..n {
            if li == l1 || li == l2 {
                continue;
            }
            let l1_i = (l1, li);
            if l_ts[&l1_i].len() == 0 {
                continue;
            }
            let d = bfs_los(n, li, l2, l_ts, ds);
            if d == -1 {
                continue;
            }
            if d <= sd {
                if d < sd {
                    lis.clear();
                }
                lis.push(li);
                sd = d;
            }
        }
        if sd == isize::MAX - 1 {
            line_os.insert(
                lp12,
                LineOptimalSet {
                    d: -1,
                    vp: HashSet::new(),
                },
            );
            return;
        }
        let mut vp = HashSet::new();
        for li in lis {
            let l = &l_ts[&(l1, li)];
            for &v in l {
                vp.insert(v);
            }
        }
        line_os.insert(lp12, LineOptimalSet { d: sd + 2, vp });
    }
}

fn compute_line_optimal_set(
    n: usize,
    l1: usize,
    l2: usize,
    line_os: &mut HashMap<(usize, usize), LineOptimalSet>,
    l_ts: &HashMap<(usize, usize), HashSet<usize>>,
    mut alr_vis: HashSet<usize>,
) {
    if line_os.contains_key(&(l1, l2)) {
        return;
    }
    let lp12 = (l1, l2);
    alr_vis.insert(l1);
    let vp = &l_ts[&lp12];
    if vp.len() > 0 {
        line_os.insert(
            lp12,
            LineOptimalSet {
                d: 1,
                vp: vp.clone(),
            },
        );
        return;
    } else {
        let mut sd = isize::MAX - 1;
        let mut sli1 = Vec::new();
        let mut sli2 = Vec::new();
        for li in 0..n {
            if li == l1 || li == l2 {
                continue;
            }
            let lp1i = (l1, li);
            if l_ts[&lp1i].len() == 0 {
                continue;
            }
            if !line_os.contains_key(&lp1i) {
                line_os.insert(
                    lp1i,
                    LineOptimalSet {
                        d: 1,
                        vp: l_ts[&lp1i].clone(),
                    },
                );
            }
            if alr_vis.contains(&li) {
                continue;
            }
            compute_line_optimal_set(n, li, l2, line_os, l_ts, alr_vis.clone());
            let di2 = &line_os[&(li, l2)];
            if di2.d == -1 {
                // line_os.insert(
                //     lp12,
                //     LineOptimalSet {
                //         d: -1,
                //         vp: HashSet::new(),
                //     },
                // );
                // return;
                continue;
            }
            // must actually store all values where di2.d <= sd + 1
            if di2.d <= sd + 1 {
                if di2.d < sd {
                    sli2.clear();
                    if di2.d < sd - 1 {
                        sli1.clear();
                    }
                    sd = di2.d;
                } else {
                    if di2.d == sd {
                        sli1.push(li);
                    } else {
                        sli2.push(li);
                    }
                }
            }
        }
        if sd == isize::MAX - 1 {
            line_os.insert(
                lp12,
                LineOptimalSet {
                    d: -1,
                    vp: HashSet::new(),
                },
            );
            return;
        }
        let mut ns = sd + 1;
        let mut vp2s = Vec::new();
        let mut vp1s = Vec::new();
        for &li in sli1.iter().chain(sli2.iter()) {
            let di2 = &line_os[&(li, l2)];
            let mut vp: HashSet<usize> =
                l_ts[&(li, l2)].intersection(&di2.vp).map(|p| *p).collect();
            let mut d = di2.d;
            if vp.len() == 0 {
                vp = l_ts[&(li, l2)].clone();
                d += 1;
            }
            if d <= ns {
                if d < ns {
                    ns = d;
                    vp1s.push(vp);
                    vp2s.clear();
                } else {
                    vp2s.push(vp);
                }
            }
        }
        let mut vp = HashSet::new();
        for svp in vp1s.iter().chain(vp2s.iter()) {
            vp = vp.union(svp).map(|p| *p).collect();
        }
        line_os.insert(lp12, LineOptimalSet { d: ns, vp });
    }
}

fn tg2_5_qry(
    q: Query,
    row_os: &HashMap<(usize, usize), LineOptimalSet>,
    column_os: &HashMap<(usize, usize), LineOptimalSet>,
) -> isize {
    if q.0 == q.2 && q.1 == q.3 {
        return 0;
    } else if q.0 == q.2 || q.1 == q.3 {
        return 1;
    } else {
        let rp = &row_os[&(q.1, q.3)];
        let cp = &column_os[&(q.0, q.2)];
        let mut rd = rp.d;
        let mut cd = cp.d;
        if rd != -1 && !rp.vp.contains(&q.1) {
            rd += 1;
        }
        if cd != -1 && !cp.vp.contains(&q.0) {
            cd += 1;
        }
        if cd < rd || rd == -1 {
            rd = cd;
        }
        if rd == -1 {
            return -1;
        }
        return rd + 1;
    }
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: TIME LIMIT EXCEEDED