結果

問題 No.922 東北きりきざむたん
ユーザー akakimidoriakakimidori
提出日時 2019-11-09 03:40:43
言語 Rust
(1.72.1)
結果
AC  
実行時間 154 ms / 2,000 ms
コード長 6,361 bytes
コンパイル時間 1,301 ms
コンパイル使用メモリ 154,484 KB
実行使用メモリ 31,516 KB
最終ジャッジ日時 2023-10-13 06:39:39
合計ジャッジ時間 5,218 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,368 KB
testcase_01 AC 1 ms
4,372 KB
testcase_02 AC 1 ms
4,368 KB
testcase_03 AC 1 ms
4,372 KB
testcase_04 AC 1 ms
4,372 KB
testcase_05 AC 1 ms
4,368 KB
testcase_06 AC 2 ms
4,368 KB
testcase_07 AC 1 ms
4,368 KB
testcase_08 AC 1 ms
4,372 KB
testcase_09 AC 43 ms
17,108 KB
testcase_10 AC 19 ms
6,776 KB
testcase_11 AC 36 ms
13,844 KB
testcase_12 AC 27 ms
18,552 KB
testcase_13 AC 10 ms
6,708 KB
testcase_14 AC 73 ms
26,648 KB
testcase_15 AC 24 ms
19,488 KB
testcase_16 AC 136 ms
29,476 KB
testcase_17 AC 124 ms
29,488 KB
testcase_18 AC 135 ms
29,392 KB
testcase_19 AC 134 ms
29,480 KB
testcase_20 AC 145 ms
29,424 KB
testcase_21 AC 154 ms
29,036 KB
testcase_22 AC 144 ms
29,032 KB
testcase_23 AC 141 ms
28,952 KB
testcase_24 AC 142 ms
28,864 KB
testcase_25 AC 126 ms
31,440 KB
testcase_26 AC 126 ms
31,516 KB
testcase_27 AC 125 ms
31,516 KB
testcase_28 AC 35 ms
24,268 KB
testcase_29 AC 105 ms
28,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

// ---------- 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 ----------
//---------- 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 ----------
use std::io::Read;

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 query: usize = it.next().unwrap().parse().unwrap();
    let mut g = vec![vec![]; n + 1];
    let mut u = union_find::UF::new(n + 1);
    let mut lca = LCA::new(n + 1);
    for _ in 0..m {
        let a: usize = it.next().unwrap().parse().unwrap();
        let b: usize = it.next().unwrap().parse().unwrap();
        g[a].push(b);
        g[b].push(a);
        lca.add_edge(a, b);
        u.unite(a, b);
    }
    for i in 1..=n {
        if i == u.root(i) {
            g[0].push(i);
            lca.add_edge(0, i);
        }
    }
    lca.build(0);
    let mut q = vec![];
    let mut stack = vec![(0, 0)];
    let mut depth = vec![0; n + 1];
    while let Some((v, p)) = stack.pop() {
        q.push(v);
        for i in 0..g[v].len() {
            if g[v][i] == p {
                g[v].remove(i);
                break;
            }
        }
        for &u in &g[v] {
            depth[u] = depth[v] + 1;
            stack.push((u, v));
        }
    }
    let mut cnt = vec![0; n + 1];
    let mut ans = 0;
    for _ in 0..query {
        let a: usize = it.next().unwrap().parse().unwrap();
        let b: usize = it.next().unwrap().parse().unwrap();
        if u.same(a, b) {
            ans += depth[a] + depth[b] - 2 * depth[lca.query(a, b)];
        } else {
            cnt[a] += 1;
            cnt[b] += 1;
        }
    }
    let mut down = vec![0; n + 1];
    let mut size = cnt.clone();
    for &v in q[1..].iter().rev() {
        for &u in &g[v] {
            down[v] += down[u] + size[u];
            size[v] += size[u];
        }
    }
    let mut up = vec![0; n + 1];
    let mut up_size = cnt.clone();
    for &v in &q[1..] {
        let mut s = up[v];
        let mut c = up_size[v];
        for &u in &g[v] {
            s += down[u] + size[u];
            c += size[u];
        }
        for &u in &g[v] {
            up[u] = s - down[u] - size[u] + c - size[u];
            up_size[u] = c - size[u] + cnt[u];
        }
    }
    let mut dp = vec![std::usize::MAX; n + 1];
    for v in 1..=n {
        let r = u.root(v);
        dp[r] = std::cmp::min(dp[r], down[v] + up[v]);
    }
    for v in 1..=n {
        if u.root(v) == v {
            ans += dp[v];
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}
0