結果

問題 No.922 東北きりきざむたん
ユーザー akakimidoriakakimidori
提出日時 2019-11-09 03:55:50
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 163 ms / 2,000 ms
コード長 6,158 bytes
コンパイル時間 13,164 ms
コンパイル使用メモリ 405,988 KB
実行使用メモリ 28,852 KB
最終ジャッジ日時 2024-09-15 03:55:57
合計ジャッジ時間 16,706 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 48 ms
16,432 KB
testcase_10 AC 20 ms
6,520 KB
testcase_11 AC 38 ms
13,236 KB
testcase_12 AC 30 ms
17,724 KB
testcase_13 AC 10 ms
6,356 KB
testcase_14 AC 86 ms
24,880 KB
testcase_15 AC 25 ms
18,848 KB
testcase_16 AC 146 ms
26,876 KB
testcase_17 AC 143 ms
26,752 KB
testcase_18 AC 140 ms
26,748 KB
testcase_19 AC 133 ms
27,000 KB
testcase_20 AC 140 ms
26,872 KB
testcase_21 AC 163 ms
26,464 KB
testcase_22 AC 153 ms
26,468 KB
testcase_23 AC 154 ms
26,468 KB
testcase_24 AC 159 ms
26,464 KB
testcase_25 AC 123 ms
28,840 KB
testcase_26 AC 122 ms
28,852 KB
testcase_27 AC 122 ms
28,836 KB
testcase_28 AC 37 ms
23,160 KB
testcase_29 AC 104 ms
26,356 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(&self, mut x: usize) -> usize {
            while self.p[x] >= 0 {
                x = self.p[x] as usize;
            }
            x
        }
        pub fn same(&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);
    }
    let u = u;
    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 = 0usize;
    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 dp = down.clone();
    let all_size = size.clone();
    for &v in &q[1..] {
        let r = u.root(v);
        let d = dp[v];
        for &u in &g[v] {
            dp[u] = d - size[u] + all_size[r] - size[u];
        }
    }
    for v in 1..=n {
        let r = u.root(v);
        dp[r] = std::cmp::min(dp[r], dp[v]);
    }
    for v in 1..=n {
        if u.root(v) == v {
            ans += dp[v];
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}
0