結果

問題 No.3079 Unite Japanese Prefectures
コンテスト
ユーザー urectanc
提出日時 2025-09-02 20:06:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 290 ms / 4,000 ms
コード長 3,493 bytes
コンパイル時間 14,765 ms
コンパイル使用メモリ 385,484 KB
実行使用メモリ 27,532 KB
最終ジャッジ日時 2025-09-02 20:06:28
合計ジャッジ時間 17,863 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize, m: usize,
        mut edges: [(Usize1, Usize1, Usize1); m]
    }
    edges.sort_unstable_by_key(|t| t.2);

    let mut count = [0; 6];
    let mut dsu = dsu::Dsu::new(n);
    for &(u, v, c) in &edges {
        if !dsu.same(u, v) {
            dsu.merge(u, v);
            count[c] += 1;
        }
    }

    let mut dp = HashMap::new();
    dp.insert([0; 6], 0f64);

    for a in 0..=count[0] {
        for b in 0..=count[1] {
            for c in 0..=count[2] {
                for d in 0..=count[3] {
                    for e in 0..=count[4] {
                        for f in 0..=count[5] {
                            let mut state = [a, b, c, d, e, f];
                            if state == [0; 6] {
                                continue;
                            }
                            let mut exp = 6.0;
                            let l = (0..6).find(|&i| state[i] > 0).unwrap();
                            for i in l..6 {
                                let target = (l..=i).rfind(|&j| state[j] > 0).unwrap();
                                state[target] -= 1;
                                exp += *dp.get(&state).unwrap();
                                state[target] += 1;
                            }
                            exp /= (6 - l) as f64;
                            dp.insert(state, exp);
                        }
                    }
                }
            }
        }
    }

    let ans = dp.get(&count).unwrap();
    println!("{ans}");
}

#[allow(dead_code)]
mod dsu {
    pub struct Dsu {
        parent_or_size: Vec<i32>,
    }

    impl Dsu {
        pub fn new(size: usize) -> Self {
            assert!(size <= i32::MAX as usize);
            Self {
                parent_or_size: vec![-1; size],
            }
        }

        pub fn clear(&mut self) {
            self.parent_or_size.fill(-1);
        }

        pub fn leader(&mut self, u: usize) -> usize {
            if self.parent_or_size[u] < 0 {
                return u;
            }
            self.parent_or_size[u] = self.leader(self.parent_or_size[u] as usize) as i32;
            self.parent_or_size[u] as usize
        }

        pub fn same(&mut self, u: usize, v: usize) -> bool {
            self.leader(u) == self.leader(v)
        }

        pub fn size(&mut self, u: usize) -> usize {
            let x = self.leader(u);
            -self.parent_or_size[x] as usize
        }

        pub fn merge(&mut self, u: usize, v: usize) -> usize {
            let (mut x, mut y) = (self.leader(u), self.leader(v));
            if x == y {
                return x;
            }
            if self.size(x) < self.size(y) {
                std::mem::swap(&mut x, &mut y);
            }
            self.parent_or_size[x] += self.parent_or_size[y];
            self.parent_or_size[y] = x as i32;
            x
        }

        pub fn groups(&mut self) -> Vec<Vec<usize>> {
            let n = self.parent_or_size.len();
            let mut result = (0..n)
                .map(|u| {
                    let size = if u == self.leader(u) { self.size(u) } else { 0 };
                    Vec::with_capacity(size)
                })
                .collect::<Vec<_>>();
            for u in 0..n {
                result[self.leader(u)].push(u);
            }
            result.into_iter().filter(|v| !v.is_empty()).collect()
        }
    }
}
0