結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー akakimidori
提出日時 2019-11-08 22:37:23
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 7,462 bytes
コンパイル時間 20,027 ms
コンパイル使用メモリ 387,476 KB
実行使用メモリ 39,016 KB
最終ジャッジ日時 2024-09-15 01:46:41
合計ジャッジ時間 19,966 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

//---------- begin union_find ----------
#[allow(dead_code)]
mod union_find {
    pub struct UF {
        p: Vec<i32>,
    }
    impl UF {
        pub fn new(n: usize) -> UF {
            UF {p: vec![-1; n] }
        }
        pub fn init(&mut self) {
            for p in self.p.iter_mut() {
                *p = -1;
            }
        }
        pub fn root(&mut self, mut x: usize) -> usize {
            while self.p[x] >= 0 {
                x = self.p[x] as usize;
            }
            x
        }
        pub fn same(&mut self, x: usize, y: usize) -> bool {
            self.root(x) == self.root(y)
        }
        pub fn unite(&mut self, mut x: usize, mut y: usize) -> Option<(usize, usize)> {
            x = self.root(x);
            y = self.root(y);
            if x == y {
                return None;
            }
            if self.p[x] > self.p[y] {
                let s = x;
                x = y;
                y = s;
            }
            self.p[x] += self.p[y];
            self.p[y] = x as i32;
            Some((x, y))
        }
        pub fn get_size(&mut self, x: usize) -> usize {
            let r = self.root(x);
            (-self.p[r]) as usize
        }
    }
}
//---------- end union_find ----------
// ---------- begin Lowest Common Ancestor ----------
struct LCA {
    graph: Vec<Vec<usize>>,
    path_root: Vec<usize>,
    path_parent: Vec<usize>,
    index: Vec<usize>
}

impl LCA {
    fn new(n: usize) -> Self {
        LCA {
            graph: vec![vec![]; n],
            path_root: vec![],
            path_parent: vec![],
            index: vec![],
        }
    }
    fn add_edge(&mut self, a: usize, b: usize) {
        self.graph[a].push(b);
        self.graph[b].push(a);
    }
    fn build(&mut self, root: usize) {
        let mut q = vec![];
        let mut stack = vec![(root, root)];
        let graph = &mut self.graph;
        while let Some((v, p)) = stack.pop() {
            q.push(v);
            for i in 0..graph[v].len() {
                if graph[v][i] == p {
                    graph[v].swap_remove(i);
                    break;
                }
            }
            for &u in &graph[v] {
                stack.push((u, v));
            }
        }
        let n = graph.len();
        let mut size = vec![1; n];
        for &v in q.iter().rev() {
            for i in 0..graph[v].len() {
                let u = graph[v][i];
                size[v] += size[u];
                if size[u] > size[graph[v][0]] {
                    graph[v].swap(0, i);
                }
            }
        }
        let mut path_root = vec![root; n];
        let mut path_parent = vec![root; n];
        let mut index = vec![n; n];
        let mut stack = vec![root];
        let mut k = 0;
        while let Some(v) = stack.pop() {
            index[v] = k;
            k += 1;
            for i in 1..graph[v].len() {
                let u = graph[v][i];
                path_root[u] = u;
                path_parent[u] = v;
                stack.push(u);
            }
            if graph[v].len() > 0 {
                let u = graph[v][0];
                path_root[u] = path_root[v];
                path_parent[u] = path_parent[v];
                stack.push(u);
            }
        }
        self.path_root = path_root;
        self.path_parent = path_parent;
        self.index = index;
    }
    fn query(&self, mut a: usize, mut b: usize) -> usize {
        let path = &self.path_root;
        let parent = &self.path_parent;
        let index = &self.index;
        while path[a] != path[b] {
            if index[a] < index[b] {
                b = parent[b];
            } else {
                a = parent[a];
            }
        }
        if index[a] < index[b] {a} else {b}
    }
}
// ---------- end Lowest Common Ancestor ----------
use std::io::Read;

fn calc(r: usize, g: &mut Vec<Vec<usize>>, cnt: &Vec<usize>, ask: &Vec<(usize, usize)>) -> usize {
    let mut q = vec![];
    let mut stack = vec![(r, r)];
    while let Some((v, p)) = stack.pop() {
        q.push(v);
        for i in 0..g[v].len() {
            if g[v][i] == p {
                g[v].swap_remove(i);
                break;
            }
        }
        for &u in &g[v] {
            stack.push((u, v));
        }
    }
    let mut z = q.clone();
    z.sort();
    let mut graph = vec![vec![]; z.len()];
    let mut que = vec![];
    let mut count = vec![0; z.len()];
    for &v in &q {
        que.push(z.binary_search(&v).unwrap());
        count[z.binary_search(&v).unwrap()] = cnt[v];
        for &u in &g[v] {
            let v = z.binary_search(&v).unwrap();
            let u = z.binary_search(&u).unwrap();
            graph[v].push(u);
        }
    }
    let g = graph;
    let q = que;
    let cnt = count;
    let n = z.len();
    let mut depth = vec![0; n];
    let mut lca = LCA::new(n);
    for &v in &q {
        for &u in &g[v] {
            depth[u] = depth[v] + 1;
            lca.add_edge(u, v);
        }
    }
    lca.build(q[0]);
    let mut ans = 0;
    for &(a, b) in ask {
        let a = z.binary_search(&a).unwrap();
        let b = z.binary_search(&b).unwrap();
        ans += depth[a] + depth[b] - 2 * depth[lca.query(a, b)];
    }
    //dp
    let mut down = vec![0; n];
    let mut sum = vec![0; n];
    for &v in q.iter().rev() {
        sum[v] = cnt[v];
        for &u in &g[v] {
            sum[v] += sum[u];
            down[v] += down[u] + sum[u];
        }
    }
    let mut up = vec![(0, 0); n];
    up[q[0]] = (0, cnt[q[0]]);
    for &v in &q {
        let mut stack = vec![up[v]];
        for &u in &g[v] {
            let (s, c) = *stack.last().unwrap();
            stack.push((s + down[u] + sum[u], c + sum[u]));
        }
        stack.pop();
        let mut add = (0, 0);
        for &u in g[v].iter().rev() {
            let (s, c) = stack.pop().unwrap();
            up[u] = (s + c + add.0 + add.1, c + add.1);
            add.0 += down[u] + sum[u];
            add.1 += sum[u];
        }
    }
    let mut local = std::usize::MAX;
    for &v in &q {
        local = std::cmp::min(local, down[v] + up[v].0);
    }
    ans + local
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let q: usize = it.next().unwrap().parse().unwrap();
    let mut g = vec![vec![]; n];
    let mut u = union_find::UF::new(n);
    for _ in 0..m {
        let a: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let b: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        u.unite(a, b);
        g[a].push(b);
        g[b].push(a);
    }
    let mut cnt = vec![0; n];
    let mut ask = vec![vec![]; n];
    for _ in 0..q {
        let a: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let b: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        if u.same(a, b) {
            let r = u.root(a);
            ask[r].push((a, b));
        } else {
            cnt[a] += 1;
            cnt[b] += 1;
        }
    }
    let mut used = vec![false; n];
    let mut ans = 0;
    for i in 0..n {
        let r = u.root(i);
        if used[r] {
            continue;
        }
        used[r] = true;
        ans += calc(r, &mut g, &cnt, &ask[r]);
    }
    println!("{}", ans);
}

fn main() {
    run();
}
0