結果
| 問題 | No.1207 グラフX |
| ユーザー |
 ikd
|
| 提出日時 | 2020-09-03 20:51:42 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 410 ms / 2,000 ms |
| コード長 | 8,158 bytes |
| コンパイル時間 | 16,165 ms |
| コンパイル使用メモリ | 380,612 KB |
| 実行使用メモリ | 58,112 KB |
| 最終ジャッジ日時 | 2024-11-24 01:14:44 |
| 合計ジャッジ時間 | 30,152 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 |
ソースコード
pub struct ProconReader<R: std::io::Read> {reader: R,}impl<R: std::io::Read> ProconReader<R> {pub fn new(reader: R) -> Self {Self { reader }}pub fn get<T: std::str::FromStr>(&mut self) -> T {use std::io::Read;let buf = self.reader.by_ref().bytes().map(|b| b.unwrap()).skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r').take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r').collect::<Vec<_>>();std::str::from_utf8(&buf).unwrap().parse().ok().expect("Parse Error.")}}#[allow(dead_code)]mod mint {use std::ops::{Add, BitAnd, Div, Mul, Rem, Shr, Sub};#[derive(Copy, Clone)]pub struct Mint<T> {x: T,mo: T,}impl<T> Mint<T>whereT: Copy,{pub fn new(x: T, mo: T) -> Mint<T> {Mint { x, mo }}}impl<T> Mint<T>whereT: Copy,{pub fn val(&self) -> T {self.x}pub fn mo(&self) -> T {self.mo}}impl<T> Add<T> for Mint<T>whereT: Copy,T: Add<Output = T>,T: Rem<Output = T>,{type Output = Mint<T>;fn add(self, rhs: T) -> Mint<T> {Mint::new((self.val() + rhs % self.mo()) % self.mo(), self.mo())}}impl<T> Add<Mint<T>> for Mint<T>whereT: Copy,Mint<T>: Add<T, Output = Mint<T>>,{type Output = Mint<T>;fn add(self, rhs: Mint<T>) -> Mint<T> {self + rhs.val()}}impl<T> Sub<T> for Mint<T>whereT: Copy,T: Add<Output = T>,T: Sub<Output = T>,T: Rem<Output = T>,{type Output = Mint<T>;fn sub(self, rhs: T) -> Mint<T> {Mint::new((self.val() + self.mo() - rhs % self.mo()) % self.mo(),self.mo(),)}}impl<T> Sub<Mint<T>> for Mint<T>whereT: Copy,Mint<T>: Sub<T, Output = Mint<T>>,{type Output = Mint<T>;fn sub(self, rhs: Mint<T>) -> Mint<T> {self - rhs.val()}}impl<T> Mul<T> for Mint<T>whereT: Copy,T: Mul<Output = T>,T: Rem<Output = T>,{type Output = Mint<T>;fn mul(self, rhs: T) -> Mint<T> {Mint::new((self.val() * rhs % self.mo()) % self.mo(), self.mo())}}impl<T> Mul<Mint<T>> for Mint<T>whereT: Copy,Mint<T>: Mul<T, Output = Mint<T>>,{type Output = Mint<T>;fn mul(self, rhs: Mint<T>) -> Mint<T> {self * rhs.val()}}impl<T> Mint<T>whereT: Copy,T: Sub<Output = T>,T: Div<Output = T>,T: PartialOrd,T: PartialEq,T: BitAnd<Output = T>,T: Shr<Output = T>,Mint<T>: Mul<Output = Mint<T>>,{pub fn pow(self, y: T) -> Mint<T> {let one = self.mo() / self.mo();let zero = self.mo() - self.mo();let mut res = Mint::one(self.mo());let mut base = self;let mut exp = y;while exp > zero {if (exp & one) == one {res = res * base;}base = base * base;exp = exp >> one;}res}}impl<T> Div<T> for Mint<T>whereT: Copy,T: Sub<Output = T>,T: Div<Output = T>,T: PartialOrd,T: PartialEq,T: BitAnd<Output = T>,T: Shr<Output = T>,Mint<T>: Mul<Output = Mint<T>>,{type Output = Mint<T>;fn div(self, rhs: T) -> Mint<T> {let one = self.mo() / self.mo();self * Mint::new(rhs, self.mo()).pow(self.mo() - one - one)}}impl<T> Div<Mint<T>> for Mint<T>whereT: Copy,Mint<T>: Div<T, Output = Mint<T>>,{type Output = Mint<T>;fn div(self, rhs: Mint<T>) -> Mint<T> {self / rhs.val()}}impl<T> Mint<T>whereT: Copy,T: Div<Output = T>,Mint<T>: Div<Output = Mint<T>>,{pub fn inv(self) -> Mint<T> {Mint::one(self.mo()) / self}}impl<T> std::fmt::Display for Mint<T>whereT: Copy + std::fmt::Display,{fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {write!(f, "{}", self.val())}}impl<T> Mint<T>whereT: Copy,T: Sub<Output = T>,{pub fn zero(mo: T) -> Mint<T> {Mint { x: mo - mo, mo }}}impl<T> Mint<T>whereT: Copy,T: Div<Output = T>,{pub fn one(mo: T) -> Mint<T> {Mint { x: mo / mo, mo }}}}use mint::Mint;pub struct UnionFind {par: Vec<usize>,size: Vec<usize>,}impl UnionFind {pub fn new(n: usize) -> UnionFind {UnionFind {par: (0..n).map(|i| i).collect::<Vec<_>>(),size: vec![1; n],}}pub fn find(&mut self, i: usize) -> usize {if self.par[i] == i {self.par[i]} else {self.par[i] = self.find(self.par[i]);self.par[i]}}pub fn unite(&mut self, i: usize, j: usize) {let i = self.find(i);let j = self.find(j);if i == j {return;}let (i, j) = if self.size[i] >= self.size[j] {(i, j)} else {(j, i)};self.par[j] = i;self.size[i] += self.size[j];}pub fn same(&mut self, i: usize, j: usize) -> bool {self.find(i) == self.find(j)}pub fn get_size(&mut self, i: usize) -> usize {let p = self.find(i);self.size[p]}}#[derive(Debug, Clone)]struct Edge {from: usize,to: usize,cost: i64,}fn minimum_spanning_tree(n: usize, edges: &Vec<Edge>) -> Option<Vec<Edge>> {let mut es = edges.clone();es.sort_by(|a, b| a.cost.cmp(&b.cost));let mut uf = UnionFind::new(n);let result = es.into_iter().filter(|e| {if !uf.same(e.from, e.to) {uf.unite(e.from, e.to);true} else {false}}).collect::<Vec<_>>();if result.len() == n - 1 {Some(result)} else {assert!(result.len() < n - 1);None}}fn dfs(g: &Vec<Vec<Edge>>, i: usize, p: usize, size: &mut Vec<usize>) {size[i] = 1;for e in &g[i] {if e.to != p {dfs(g, e.to, i, size);size[i] += size[e.to];}}}fn main() {let stdin = std::io::stdin();let mut rd = ProconReader::new(stdin.lock());let n: usize = rd.get();let m: usize = rd.get();let x: usize = rd.get();let mut edges = vec![];for _ in 0..m {let u: usize = rd.get();let v: usize = rd.get();let w: i64 = rd.get();edges.push(Edge {from: u - 1,to: v - 1,cost: w,});}let tree_edges = minimum_spanning_tree(n, &edges).unwrap();let mut g = vec![vec![]; n];for e in &tree_edges {g[e.from].push(e.clone());g[e.to].push(Edge {from: e.to,to: e.from,..*e});}let mut size = vec![0; n];dfs(&g, 0, !0, &mut size);let mo = 1_000_000_000 + 7;let mut ans = Mint::zero(mo);for i in 0..n {for e in &g[i] {if size[e.to] < size[i] {ans = ans+ Mint::new(size[e.to] * (n - size[e.to]), mo)* Mint::new(x, mo).pow(e.cost as usize);}}}println!("{}", ans);}